代码随想录动day单调栈

739.每日温度

一般用单调栈，就是解决一维数组寻找任一元素的右边或者左边第一个比自己大或者比自己小的位置。
暴力法的时间复杂度O（n*n）,但是单调栈可以用时间换空间。
这道题是寻找元素右边第一个比自己大的，所以（单调栈从栈头到栈底的）顺序为递增。

class Solution {
public:
    vector<int> dailyTemperatures(vector<int>& temperatures) {
        vector<int> result(temperatures.size(),0);
        stack<int> st;
        st.push(0);
        //cout<<"ni"<
        for(int i=1;i<temperatures.size();i++){
            if(temperatures[st.top()]<temperatures[i]){
                while(!st.empty() && temperatures[st.top()]<temperatures[i]){
                    result[st.top()]=i-st.top();
                //cout<
                    st.pop();
                }
                st.push(i);
            }
            else if(temperatures[st.top()]>=temperatures[i]){
                st.push(i);
            }
        }
        return result;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

496.下一个更大元素I

在上一题基础上改为两个数组
用Map的关键字储存数组1的值，map[key]=下标

class Solution {
public:
    vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {
        vector<int> result(nums1.size(),-1);
        stack<int> st;
        st.push(0);
        unordered_map<int, int> umap;
        for (int i = 0; i < nums1.size(); i++) {
            umap[nums1[i]] = i;
        }
        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()]) {
                    if (umap.count(nums2[st.top()]) > 0) { // 看map里是否存在这个元素
                        int index = umap[nums2[st.top()]]; // 根据map找到nums2[st.top()] 在 nums1中的下标
                        result[index] = nums2[i];
                    }
                    st.pop();
                }
                st.push(i);
            }
        }
        return result;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

503.下一个更大元素

在上上题基础上，改为队列数组。

42.接雨水

接雨水这道题目需要寻找一个元素，右边最大元素以及左边最大元素，来计算雨水面积。
单调栈是按照行方向来计算雨水

class Solution {
public:
    int trap(vector<int>& height) {
        int sum=0;
        stack<int> st;
        st.push(0);
        for(int i=1;i<height.size();i++){
            if(height[i]<=height[st.top()]){
                st.push(i);
            }
            else{
                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;
                        sum+=h*w;
                    }
                }
                st.push(i);
            }
        }
        return sum;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

84.柱状图的最大矩形

本题是要找每个柱子左右两边第一个小于该柱子的柱子，所以从栈头（元素从栈头弹出）到栈底的顺序应该是从大到小的顺序，与接雨水的题相反。
在 height数组上后，都加了一个元素0。
如果数组本身就是升序的，例如[2,4,6,8]，那么入栈之后 都是单调递减，一直都没有走 情况三 计算结果的哪一步，所以最后输出的就是0了。如果数组本身是降序的，例如 [8,6,4,2]，在 8 入栈后，6 开始与8 进行比较，此时我们得到 mid（8），rigt（6），但是得不到 left。