代码随想录算法训练营刷题复习4 ：单调栈

单调栈

单调栈
如果题目出现典型的
【左小 中大(栈中左侧元素都比此值小) || 右小】（寻找右侧第一个比此值小的元素）
【左大 中小(栈中左侧元素都比此值大) || 右大】（寻找右侧第一个比此值大的元素）
数据关系的话，可以考虑使用单调栈解决问题

1. 739. 每日温度

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

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

4. 42. 接雨水

5. 84. 柱状图中最大的矩形这个题忽略了对数组头和尾添加0以方便对头和尾元素的处理

4、5这两个题可以总结为单调栈中求面积问题：找所求区域的高和宽

739. 每日温度

class Solution {
public:
    vector<int> dailyTemperatures(vector<int>& temperatures) {
        if(temperatures.size()<=1)
            return vector<int>(0);
        //需要用到栈和数组
        stack<int> st;
        vector<int> result(temperatures.size(),0);
        // 初始化把第一个元素的下标入栈
        st.push(0);
        for(int i=1;i<temperatures.size();i++) {
            //栈顶的元素值与当前遍历的值作比较
            if(temperatures[i] <= temperatures[st.top()]) {
                st.push(i);
            }
            else {
                //遇到第一个比当前值大的值时，用while循环来循环处理
                while(!st.empty() && temperatures[i] > temperatures[st.top()])
                {
                    result[st.top()] = i-st.top();
                    st.pop();
                }
                //处理结束说明栈中已经没有比当前遍历元素还小的值了，就把i入栈
                st.push(i);
            }
        }
        return result;
        
    }
};

496. 下一个更大元素 I

class Solution {
public:
    vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {
        unordered_map<int,int> umap;
        //想要存 <键值,下标>这个关系
        // 下文中需要判断nums2中的值是否在nums1中出现，下标零出现误判，故使用i+1
        for(int i=0;i<nums1.size();i++) {
            umap[nums1[i]]=i+1;
        }

        if(nums1.size()==0 || nums2.size()==0)
            return vector<int>(nums1.size(),-1);
        
        stack<int> st;
        vector<int> ans(nums1.size(),-1);
        //这个数据没必要存了其实
        // vector temp(nums2.size(),-1);
        st.push(0);
        for(int i=1;i<nums2.size();i++) {
            if(nums2[i] <= nums2[st.top()]) {
                st.push(i);
            }
            else {
                while(!st.empty() && nums2[i] > nums2[st.top()]) {
                    // temp[st.top()] = nums2[i];
                    if(umap[nums2[st.top()]]!=0) {
                        ans[umap[nums2[st.top()]] -1] = nums2[i];
                    }
                    st.pop();
                }
                st.push(i);
            }
        }
        return ans;
    }
};

503. 下一个更大元素 II

class Solution {
public:
    vector<int> nextGreaterElements(vector<int>& nums) {
        //通过复制数组，将循环问题转化为不循环问题
        vector<int> nums1(nums.begin(),nums.end());
        // insert函数参数需要，插入位置，以及插入的元素范围
        nums.insert(nums.end(),nums1.begin(),nums1.end());

        stack<int> st;
        vector<int> res(nums.size(),-1);
        st.push(0);
        for(int i=1;i<nums.size();i++) {
            if(nums[i]<=nums[st.top()]) {
                st.push(i);
            }
            else {
                while(!st.empty() && nums[i]>nums[st.top()] ) {
                    res[st.top()] = nums[i];
                    st.pop();
                }
                st.push(i);
            }
        }
        //恢复原先数组大小
        res.resize(nums.size()/2);
        return res;
    }
};

42. 接雨水

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

84. 柱状图中最大的矩形

class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        if(heights.size()==0)
            return 0;
        if(heights.size()==1)
            return heights[0];
        
        //这里对原始数组的头尾添加0值忘记考虑了
        heights.insert(heights.begin(),0);
        heights.push_back(0);
        
        stack<int> st;
        int res=0;
        st.push(0);
        for(int i=1;i<heights.size();i++) {
            if(heights[i]>heights[st.top()])
                st.push(i);
            else if(heights[i] == heights[st.top()]) {
                st.pop();
                st.push(i);
            }
            else {
                while(!st.empty() && heights[i]< heights[st.top()]) {
                    int mid = st.top();
                    st.pop();
                    if(!st.empty()) {
                        int left = st.top();
                        int w = i-left-1;
                        res = max(res,w*heights[mid]);
                    }
                }
                st.push(i);
            }
        }
        return res;
    }
};