普通栈

先进后出的特点

​​​​​​20. 有效的括号

class Solution {
public:
    unordered_map<char, char> mp = {
        {')', '('},
        {']', '['},
        {'}', '{'}
    };

    bool isValid(string s) {
        stack<char> st;
        for (char c : s) {
            if (c == '(' || c == '[' || c == '{') {
                st.push(c);
            } else {
                if (!st.empty() && mp[c] == st.top()) {
                    st.pop();
                } else {
                    return false;
                }
            }
        }
        return st.empty();
    }
};

155. 最小栈

class MinStack {
private:
    stack<int> xStack; // 存放正常数据
    stack<int> minStack; // 顺序存放元素对应的最小值
public:
    MinStack() {

    }
    
    void push(int val) {
        xStack.push(val);
        if (!minStack.empty()) {
            minStack.push(min(minStack.top(), val));
        } else {
            minStack.push(val);
        }
    }
    
    void pop() {
        xStack.pop();
        minStack.pop();
    }
    
    int top() {
        return xStack.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();
 */

946. 验证栈序列

class Solution {
public:
    bool validateStackSequences(vector<int>& pushed, vector<int>& popped) {
        stack<int> st;
        for (int i = 0, j = 0; i < pushed.size(); ++i) {
            st.push(pushed[i]);
            while (!st.empty() && st.top() == popped[j]) {
                st.pop();
                ++j;
            }
        }
        return st.empty();
    }
};

394. 字符串解码

class Solution {
public:
    string getDigits(string& s, int& ptr) {
        string res;
        while (isdigit(s[ptr])) {
            res.push_back(s[ptr++]);
        }
        return res;
    }

    string getString(vector<string> &v) {
        string ret;
        for (const auto &s: v) {
            ret += s;
        }
        return ret;
    }

    string decodeString(string s) {
        vector<string> stk;
        int ptr = 0;

        while (ptr < s.size()) {
            char cur = s[ptr];
            if (isdigit(cur)) {
                string digits = getDigits(s, ptr);
                stk.push_back(digits);
            } else if (isalpha(cur) || cur == '[') {
                stk.push_back(string(1, cur));
                ptr++;
            } else {
                ptr++;
                vector<string> sub;
                while (stk.back() != "[") {
                    sub.push_back(stk.back());
                    stk.pop_back();
                }
                stk.pop_back();
                int repTIme = stoi(stk.back());
                stk.pop_back();

                string subStr;
                while (!sub.empty()) {
                    subStr += sub.back();
                    sub.pop_back();
                }

                string tmp;
                while (repTIme--) {
                    tmp += subStr;
                }
                stk.push_back(tmp);
            }
        }
        return getString(stk);
    }
};

单调栈

单调栈用途不太广泛，只处理一类典型的问题，比如「下一个更大元素」，「上一个更小元素」等。

739. 每日温度

class Solution {
public:
    vector<int> dailyTemperatures(vector<int>& temperatures) {
        // 单调递减栈，即从底到顶逐渐递减
        stack<int> st;
        vector<int> res(temperatures.size());

        for (int i = 0; i< temperatures.size(); ++i) {
            while (!st.empty() && temperatures[i] > temperatures[st.top()]) {
                int preIndex = st.top();
                res[preIndex] = i - preIndex;
                st.pop();
            }
            st.push(i);
        }
        return res;
    }
};

496. 下一个更大元素 I

双数组

class Solution {
public:
    vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {
        stack<int> st;
        unordered_map<int, int> mp;
        vector<int> res;

        for (int i = 0; i <  nums2.size(); ++i) {
            while (!st.empty() && nums2[i] > st.top()) {
                int preVal = st.top();
                st.pop();
                mp[preVal] = nums2[i];
            }
            st.push(nums2[i]);
        }

        for (auto num : nums1) {
            if (mp.find(num) != mp.end()) {
                res.push_back(mp[num]);
            } else {
                res.push_back(-1);
            }
        }
        return res;
    }
};

503. 下一个更大元素 II

循环数组

class Solution {
public:
    vector<int> nextGreaterElements(vector<int>& nums) {
        int len = nums.size();
        
        stack<int> st;
        vector<int> res(len, -1);

        
        for (int i = 0; i <  2 * len; ++i) {
            int index = i % len;
            while (!st.empty() && nums[index] > nums[st.top()]) {
                int preIndex= st.top();
                st.pop();
                res[preIndex] = nums[index];
            }
            st.push(index);
        }

        return res;
    }
};

84. 柱状图中最大的矩形

class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        int n = heights.size();
        stack<int> st;

        // 假设 h=heights[i]是矩形的高度，那么矩形的宽度最大是多少？我们需要知道：
        // 1. 在 i 左侧的小于 h 的最近元素的下标 left
        // 2. 在 i 右侧的小于 h 的最近元素的下标 right
        vector<int> left(n, 0), right(n, n);

        for (int i = 0; i < n; ++i) {
            while (!st.empty() && heights[i] < heights[st.top()]) {
                int index = st.top();
                st.pop();
                right[index] = i;
            }
            left[i] = st.empty() ? -1 : st.top();
            st.push(i);
        }

        int res = 0;
        for (int i = 0; i < n; ++i) {
            int height = heights[i];
            int wide = right[i] - left[i] - 1;
            res = max(res, height * wide);
        }
        return res;
    }
};

42. 接雨水

单调栈解法：

【Leetcode每日打卡】接雨水问题的超完全手册 - 知乎 (zhihu.com)

class Solution {
public:
    int trap(vector<int>& height) {
        stack<int> st;
        int res = 0;

        for (int i = 0; i < height.size(); ++i) {
            while (!st.empty() && height[i] > height[st.top()]) {
                int bottomIndex = st.top();
                st.pop();
                while (!st.empty() && height[bottomIndex] == height[st.top()]) {
                    st.pop();
                }

                if (!st.empty()) {
                    int heightDiff = min(height[st.top()], height[i]) - height[bottomIndex];
                    int wide = i - st.top() - 1;
                    res += heightDiff * wide;
                }
                
            }
            st.push(i);
        }
        return res;
    }
};

动态规划解法：找到第i个元素左右最大的值得较小值，减去当前高度，即为该列能存储的雨水

class Solution {
public:
    int trap(vector<int>& height) {
        int len = height.size();
        int sum = 0;

        vector<int> left_h(height.size());
        vector<int> right_h(height.size());

        for (int i = 1; i < len; ++i) {
            left_h[i] = max(left_h[i-1], height[i-1]);
        }

        for (int j = len - 2; j >= 0; --j) {
            right_h[j] = max(right_h[j+1], height[j+1]);
        }

        for (int i = 1; i < len - 1; ++i) {
            int min_h = min(left_h[i], right_h[i]);
            if (min_h > height[i]) {
                sum += min_h - height[i];
            }
        }
        return sum;
    }
};

双指针解法：

class Solution {
public:
    int trap(vector<int>& height) {
        int len = height.size();
        int sum = 0;
        int left = 0, right = len - 1;
        int left_max = 0, right_max = 0;

        while (left < right) {
            if (height[left] < height[right]) {
                if (left_max <= height[left]) {
                    left_max = height[left];
                } else {
                    sum += left_max - height[left];
                }
                ++left;
            } else {
                if (right_max <= height[right]) {
                    right_max = height[right];
                } else {
                    sum += right_max - height[right];
                }
                --right;
            }
        }
        return sum;
    }
};