More content：力扣题记之栈

栈：stack<int> sk;

队列：

• queue<TreeNode*> q; 单端队列
• deque<char> dq; 双端队列(更底层)

20. 有效的括号✅

刷包浆的题

class Solution {
public:
    bool isValid(string s) {
        unordered_map<char, char> mp;
        mp[')'] = '(';
        mp[']'] = '[';
        mp['}'] = '{';
        stack<char> sk;

        for(const char &c : s) {
            if(!sk.empty() && mp[c] == sk.top()) sk.pop();
            else sk.push(c);
        }

        return sk.empty();
    }
};

---

155. 最小栈❌

尝试用两个栈或者一栈一堆实现，都失败了

主要是一开始没想到另一个辅助栈要存放的是对应主栈不同时期的最小值

class MinStack {
private:
    stack<int> sk;
    stack<int> mmin_sk; 
public:
    MinStack() {
        mmin_sk.push(INT_MAX); //避免在向辅助栈加元素时还要先判断栈是否为空
    }
   
    void push(int val) {
        sk.push(val);

        if(val < mmin_sk.top()) mmin_sk.push(val);
        else mmin_sk.push(mmin_sk.top());
    }
    
    void pop() {
        sk.pop();
        mmin_sk.pop();
    }
    
    int top() {
        return sk.top();
    }
    
    int getMin() {
        return mmin_sk.top();
    }
};

---

394. 字符串解码❌

如何处理数字与后续字符串的关系？一个栈够吗？

由里向外拆解：3[a2[c]]→3[acc]→accaccacc

class Solution {
public:
    string decodeString(string s) {
        stack<int> num_sk;
        stack<string> str_sk;
        int num = 0;
        string res = ""; //与栈交互 逐步丰富自己

        for(const char &c : s) {
            if(c >= '0' && c <= '9') {
                num = num * 10 + c - '0'; //*10针对几位字符组成一个多位数字的情况
            } else if(c == '[') { //把数字入栈，把之前累积的字符串入栈
                num_sk.push(num);
                num = 0;
                str_sk.push(res);
                res = "";
            } else if(c == ']') { //处理与之相对应的[之间的部分
                int cnt = num_sk.top();
                num_sk.pop();
                while(cnt--) {
                    str_sk.top() += res;
                }
                res = str_sk.top();
                str_sk.pop();
            } else if(c >= 'a' && c <= 'z') {
                res += c;
            }
        }

        return res;
    }
};

ps：单调栈讲解https://leetcode.cn/problems/daily-temperatures/solutions/2811416/dai-ni-xue-hui-dan-diao-zhan-ji-chu-zhi-eqpen

---

739. 每日温度❌

单调栈常用场景：在 O(n) 的时间复杂度内求出数组中各个元素右侧或左侧第一个更大/更小的元素及其下标

class Solution {
public:
    vector<int> dailyTemperatures(vector<int>& temperatures) {
        stack<int> sk; //保持栈内元素非递增
        vector<int> res(temperatures.size(), 0); //先放入n个0

       
        for(int i = 0; i < temperatures.size(); i++) {
            while(!sk.empty() && temperatures[i] > temperatures[sk.top()]) {
                res[sk.top()] = i - sk.top();
                sk.pop();
            } 
            sk.push(i); //注意栈存的是下标
        }

        return res;
    }
};

---

84. 柱状图中最大的矩形

跟42. 接雨水很类似，栈顶和栈顶的下一个元素以及要入栈的三个元素组成了求最大面积的高和宽

class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        int res = 0;
        stack<int> sk; //递增单调栈
        sk.push(0);

        heights.push_back(0); //避免数组本身完全递增，无法触发计算条件
        heights.insert(heights.begin(), 0); //避免数组本身完全递减，取不到left
// [0,2,1,5,6,2,3,0]
// i = 5
// 0 1      mid = 3
// 0 2   
        for(int i = 1; i < heights.size(); i++) {
            while(heights[i] < heights[sk.top()]) {
                int mid = sk.top();
                sk.pop();
                int h = heights[mid];  
                int w = i - sk.top() - 1;  
                res = max(res, h * w);  
                // cout << "i = " << i << ", h = " << h << ", w = " << w << ", res = " << res << endl; 
            }
            sk.push(i);
        }

        return res;
    }
};