力扣hot100—

力扣hot100——栈

20. 有效的括号

class Solution {
public:bool isValid(string s) {stack<char> stk;auto check = [&](char ch) -> bool {if (stk.empty()) return false;char t = stk.top();if (t == '(' && ch == ')') return true;if (t == '{' && ch == '}') return true;if (t == '[' && ch == ']') return true;return false;};for (auto ch : s) {if (ch == '(' || ch == '[' || ch == '{') stk.push(ch);else {if (check(ch)) stk.pop();else return false;}}return stk.empty();}
};

栈模拟即可

155. 最小栈

class MinStack {
public:stack<int> stk1;stack<int> stk2;MinStack() {stk2.push(INT_MAX);}void push(int x) {stk1.push(x);if (x <= stk2.top()) stk2.push(x);}void pop() {int x = stk1.top();stk1.pop();if (stk2.top() == x) stk2.pop();}int top() {return stk1.top();}int getMin() {return stk2.top();}
};

stk1正常的栈，stk2维护栈的最小值，每次入栈时判断x是不是小于等于stk2.top(), 如果不是根据栈后进先出的特性，就算push进stk2是冗余的

394. 字符串解码

class Solution {
public:string decodeString(string s) {string str = "";int k = 0;stack<int> stk1;stack<string> stk2;for (int i = 0; i < s.size(); i++) {if (s[i] == '[') {stk1.push(k);stk2.push(str);k = 0;str = "";}else if (s[i] == ']') {int t = stk1.top();stk1.pop();string tmp = stk2.top();stk2.pop();for (int i = 0; i < t; i++) tmp += str;str = tmp;}else if (s[i] >= '0' && s[i] <= '9') k = k * 10 + s[i] - '0';else str += s[i];}return str;}
};

两个栈，一个栈“外层”的放大倍数，另一个栈存外层，但是不参与本次循环的字符串

739. 每日温度

class Solution {
public:vector<int> dailyTemperatures(vector<int>& a) {stack<int> stk;vector<int> ans;for (int i = a.size() - 1; i >= 0; i--) {while (stk.size() && a[i] >= a[stk.top()]) stk.pop();if (stk.empty()) ans.push_back(0);else ans.push_back(stk.top() - i);stk.push(i);}reverse(ans.begin(), ans.end());return ans;}
};

单调栈

84. 柱状图中最大的矩形

class Solution {
public:int largestRectangleArea(vector<int>& heights) {int n = heights.size();vector<int> a(n + 2);a[0] = -1;for (int i = 1; i <= n; i++) a[i] = heights[i - 1];a[n + 1] = -1;heights.clear();int ans = 0;stack<int> stk;stk.push(0);vector<int> l(n + 2, 0);vector<int> r(n + 2, 0);for (int i = 1; i <= n; i++) {while (stk.size() && a[i] <= a[stk.top()]) stk.pop();if (stk.size()) l[i] = stk.top();stk.push(i);}while (stk.size()) stk.pop();stk.push(n + 1);for (int i = n; i >= 1; i--) {while (stk.size() && a[i] <= a[stk.top()]) stk.pop();if (stk.size()) r[i] = stk.top();stk.push(i);}for (int i = 1; i <= n; i++) {ans = max(ans, (r[i] - l[i] - 1) * a[i]);}return ans;}
};