7.单调栈

LeetCode.739.每日温度

class Solution {
public:
    vector<int> dailyTemperatures(vector<int>& temperatures) {
        int n = temperatures.size();
        vector<int> ans(n);
        stack<int> s;
        for(int i = 0;i < n;i++){
            while(!s.empty() && temperatures[i] > temperatures[s.top()]){
                int pre = s.top();
                ans[pre] = i - pre;
                s.pop();
            }
            s.push(i);
        }
        return ans;
    }
};

LeetCode.496.下一个更大元素I

class Solution {
public:
    vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {
        unordered_map<int,int> hashmap;
        stack<int> st;
        for (int i = nums2.size() - 1; i >= 0; --i) {
            int num = nums2[i];
            while (!st.empty() && num >= st.top()) {
                st.pop();
            }
            hashmap[num] = st.empty() ? -1 : st.top();
            st.push(num);
        }
        vector<int> res(nums1.size());
        for (int i = 0; i < nums1.size(); ++i) {
            res[i] = hashmap[nums1[i]];
        }
        return res;
    }
};

LeetCode.503.下一个更大元素II

// 注意第二次遍历不要让后续的结果覆盖
class Solution {
public:
    vector<int> nextGreaterElements(vector<int>& nums) {
        int n = nums.size();
        unordered_map<int,int> hash;
        stack<int> s;
        vector<int> anss(n);
        for(int i = 0;i < n*2-1;i++){
            int ri = i%n;
            while(!s.empty() && nums[s.top()] < nums[ri]){
                hash[s.top()] = nums[ri];
                s.pop();
            }
            s.push(ri);
        }
        while(!s.empty()){
            if (hash.find(s.top()) == hash.end()) hash[s.top()] = -1;
            s.pop();
        }
        for(int i = 0;i < n;i++){
            anss[i] = hash[i];
        }
        return anss;
    }
};

LeetCode.42.接雨水

class Solution {
public:
    int trap(vector<int>& height) {
        stack<int> st;
        st.push(0);
        int anss = 0;
        for(int i = 1;i < height.size();i++){
            if(height[i] < height[st.top()]){
                st.push(i);
            }
            if(height[i] == height[st.top()]){
                st.pop();
                st.push(i);
            }
            if(height[i] > height[st.top()]){
                while (!st.empty() && height[i] > height[st.top()]){
                    int mid = st.top();
                    st.pop();
                    if(!st.empty()){
                        int h = min(height[st.top()], height[i]) - height[mid];
                        int w = i - st.top() - 1;
                        anss += h * w;
                    }
                }
                st.push(i);
            }
        }
        return anss;
    }
};

LeetCode.82.柱状图中最大的矩形

class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        stack<int> st;
        heights.insert(heights.begin(), 0);
        heights.push_back(0);
        st.push(0);
        int anss = 0;
        for(int i = 1;i < heights.size();i++){
            if(heights[i] > heights[st.top()]){
                st.push(i);
            }
            if(heights[i] == heights[st.top()]){
                st.pop();
                st.push(i);
            }
            if(heights[i] < heights[st.top()]){
                while (!st.empty() && heights[i] < heights[st.top()]){
                    int mid = st.top();
                    st.pop();
                    if(!st.empty()){
                        int left = st.top();
                        int right = i;
                        int w = right - left - 1;
                        int h = heights[mid];
                        anss = max(anss, w * h);
                    }
                }
                st.push(i);
            }
        }
        return anss;
    }
};