力扣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;
    }
};

求出每根柱子左边小于它的最近下标和右边小于它的最近下标，正着反着跑两遍单调栈即可