Monotonic Stack_Leetcode

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

class Solution {
public:
    vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {
        stack<int> st;
        int n = nums1.size();
        vector<int> result(n, -1);
        unordered_map<int, int> mp;
        // 记录nums1里元素的下标
        for(int i = 0; i < n; i++){
            mp[nums1[i]] = i;
        }
        st.push(0);
        for(int i = 1; i < nums2.size(); i++){
            while(!st.empty() && nums2[i] > nums2[st.top()]){
                // 元素是否存在
                if(mp.count(nums2[st.top()]) > 0){  
                    int index = mp[nums2[st.top()]];
                    result[index] = nums2[i];
                }
                st.pop();
            }
            st.push(i);
        }
        return result;
    }
};

class Solution {
public:
    vector<int> nextGreaterElements(vector<int>& nums) {
        int n = nums.size();
        vector<int> result(n, -1);
        stack<int> st;
        for(int i = 0; i < n * 2; i++){
            while(!st.empty() && nums[i % n] > nums[st.top()]){
                result[st.top()] = nums[i % n];
                st.pop();
            }
            st.push(i % n);
        }
        return result;
    }
};

class Solution {
public:
    int trap(vector<int>& height) {
        stack<int> st;   //栈内保持从底向上递减的次序
        st.push(0); 
        int sum = 0;
        for(int i=1;i<height.size();i++){
            while(!st.empty() && height[i]>height[st.top()]){ //不断弹出的过程
                int mid = height[st.top()];
                st.pop();                 //取出凹点的点
                if(!st.empty()){
                    int h = min(height[i],height[st.top()]) - mid;   //求高度（木桶效应）
                    int w = i - st.top() - 1;    //宽度
                    sum += h*w;      //累加
                }
            }
            st.push(i);   
        }
        return sum;
    }
};

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