单调栈

三步走：（这个三步走一开始有点难理解，可以刷了几道题回来再理解）

1. 维护一个单调栈
2. 处理结果
3. 插入栈

496. 下一个更大元素 I

class Solution {
public:
    vector<int> nextGreaterElement(vector<int>& v1, vector<int>& v2) {
        // 单调栈 + map
        map<int,int> m;
        stack<int> s;
        vector<int> ans;
        for(int i = v2.size() - 1 ; i >= 0; --i){
            // 1. 维护单调栈， 这里是栈顶最小
            int n = v2[i];
            while( s.size() && n >= s.top() ) s.pop();
            // 2. 处理结果
            m[n] = s.empty() ? -1 : s.top();
            // 3. 插入栈
            s.push(n);
        }
        // map
        for(int val : v1){
            ans.push_back(m[val]);
        }
        return ans;
    }
};

503. 下一个更大元素 II

class Solution {
public:
    vector<int> nextGreaterElements(vector<int>& v) {
        // 单调栈, 这里是栈顶最小
        int n = v.size();
        stack<int> s;
        vector<int> ans(n,-1);
        for(int i = 2*n -1; i>=0 ;--i){
            // 1.维护单调栈
            while(s.size() && v[i%n] >= s.top()) s.pop();
            // 2.处理结果
            ans[i%n] = s.empty() ? -1 : s.top();
            // 3.插入栈
            s.push(v[i%n]);
        }
        return ans;
    }
};

1019. 链表中的下一个更大节点

class Solution {
public:
    vector<int> nextLargerNodes(ListNode* head) {
        // 单调栈
        vector<int> v;
        stack<int> s;
        // 转换成vector
        while(head) v.push_back(head->val),head=head->next;
        int n = v.size();
        vector<int> ans(n,0);
        for(int i = n-1; i>= 0; --i){
            // 1. 维护单调栈, 这里是栈顶最小
            while( s.size() && v[i] >= s.top()) s.pop();
            // 2. 处理结果
            ans[i] = s.empty() ? 0 : s.top();
            // 3. 插入栈
            s.push(v[i]);
        }
        return ans;
    }
};

难度升级，开始变种：

739. 每日温度

class Solution {
public:
    vector<int> dailyTemperatures(vector<int>& v) {
        // 单调栈 ， 栈顶是最小温度对应的index
        int n = v.size();
        stack<int> s;
        vector<int> ans(n,0);
        for(int i = n-1;i>=0;--i){
            int cur = v[i];
            // 1.维护栈
            while(s.size() && cur >= v[s.top()]) s.pop();
            // 2.处理结果
            ans[i] = s.empty() ? 0 : s.top() - i;
            // 3.插入栈
            s.push(i);
        }
        return ans;
    }
};

难度升级

1081. 不同字符的最小子序列

class Solution {
public:
    string smallestSubsequence(string s) {
        // 单调栈，栈顶元素更大
        stack<char> st;
        unordered_map<char,int> cnt;
        unordered_map<char,int> inst;
        for(auto& val : s) ++cnt[val];
        for(int i=0;i<s.size();i++){
            char c = s[i];
            if(inst[c]){
                --cnt[c];
                continue;
            }
            // 1. 维护栈
            while(!st.empty() && c<st.top() && cnt[st.top()]>0){
                inst[st.top()] = false;
                st.pop();
            }
            // 3. 入栈
            st.push(c);
            inst[c] = true;
            --cnt[c];
        }
        // 2. 处理结果
        string ans;
        while(!st.empty()){
            ans = st.top() + ans;
            st.pop();
        }
        return ans;
    }
};

402. 移掉 K 位数字

class Solution {
public:
    string removeKdigits(string num, int k) {
        stack<char> s;
        // 单调栈
        for(auto& val : num){
            // 1. 维护单调栈
            while(s.size() && k>0 && val<s.top()){
                s.pop();
                k--;
            }
            // 3. 入栈
            s.push(val);
        }
        while(k){
            s.pop();
            k--;
        }
        // 2. 处理结果 去掉前缀"0"，方法有点憨憨
        string ans ;
        stack<char> tmp;
        while(!s.empty()){
            tmp.push(s.top());
            s.pop();
        }
        while(!tmp.empty() && tmp.top()=='0'){
            tmp.pop();
        }
        while(!tmp.empty()){
            ans = ans + tmp.top();
            tmp.pop();
        }
        return ans.empty() ? "0" : ans;
        
    }
};

其他单调栈：

84. Largest Rectangle in Histogram

1673. Find the Most Competitive Subsequence