LeetCode Hot 100：栈
20. 有效的括号
class Solution {
public:bool isValid(string s) {stack<char> stk;for (char& c : s) {if (c == ')') {if (stk.empty() || stk.top() != '(')return false;elsestk.pop();} else if (c == ']') {if (stk.empty() || stk.top() != '[')return false;elsestk.pop();} else if (c == '}') {if (stk.empty() || stk.top() != '{')return false;elsestk.pop();} elsestk.push(c);}return stk.empty();}
};
155. 最小栈
class MinStack {
private:stack<int> s, minStack;public:MinStack() {}void push(int val) {s.push(val);if (minStack.empty() || val <= minStack.top())minStack.push(val);}void pop() {int x = s.top();s.pop();if (!minStack.empty() && minStack.top() == x)minStack.pop();}int top() { return s.top(); }int getMin() { return minStack.top(); }
};/*** Your MinStack object will be instantiated and called as such:* MinStack* obj = new MinStack();* obj->push(val);* obj->pop();* int param_3 = obj->top();* int param_4 = obj->getMin();*/
394. 字符串解码
class Solution {
public:string decodeString(string s) {int n = s.size();int i = 0;stack<string> stk;while (i < n) {char c = s[i];if (isdigit(c)) {string num;while (isdigit(s[i])) {num.push_back(s[i]);i++;}stk.push(num);} else if (isalpha(c) || c == '[') {stk.push(string(1, s[i]));i++;} else { // c == ']'vector<string> sub;while (stk.top() != "[") {sub.insert(sub.begin(), stk.top());stk.pop();}stk.pop(); // 左括号出栈// 此时栈顶为当前 sub 对应的字符串应该出现的次数int repeatTime = stoi(stk.top());stk.pop();string temp;while (repeatTime--) {for (string& str : sub)temp += str;}stk.push(temp);i++;}}string ans;while (!stk.empty()) {ans.insert(0, stk.top());stk.pop();}return ans;}
};
739. 每日温度
思路 1：单调栈
class Solution {
public:vector<int> dailyTemperatures(vector<int>& temperatures) {int n = temperatures.size();vector<int> ans(n, 0);stack<int> s;for (int i = 0; i < n; i++) {int cur = temperatures[i];while (!s.empty() && cur > temperatures[s.top()]) {int j = s.top();s.pop();ans[j] = i - j;}s.push(i);}return ans;}
};
84. 柱状图中最大的矩形
class Solution {
public:int largestRectangleArea(vector<int>& heights) {int n = heights.size();// left[i] = 在 i 左侧的小于 heights[i] 的最近元素的下标vector<int> left(n, -1);stack<int> s;for (int i = 0; i < n; i++) {while (!s.empty() && heights[i] <= heights[s.top()])s.pop();if (!s.empty())left[i] = s.top();s.push(i);}// left[i] = 在 i 右侧的小于 heights[i] 的最近元素的下标vector<int> right(n, n);s = stack<int>();for (int i = n - 1; i >= 0; i--) {while (!s.empty() && heights[i] <= heights[s.top()])s.pop();if (!s.empty())right[i] = s.top();s.push(i);}int ans = INT_MIN;for (int i = 0; i < n; i++) {int len = right[i] - left[i] - 1;ans = max(ans, heights[i] * len);}return ans;}
};