代码随想录1刷—单调栈篇

什么时候想到单调栈？

• 通常是一维数组，要寻找任一个元素的右边或者左边第一个比自己大或者小的元素的位置，此时就要想到可以用单调栈了。时间复杂度为O(n)。

单调栈的原理？

• 单调栈的本质是空间换时间，因为在遍历的过程中需要用一个栈来记录右边第一个比当前元素高的元素，优点是只需要遍历一次。

• 在使用单调栈的时候首先要明确如下几点：

  • 单调栈里存放的元素是什么？
    • 单调栈里只需要存放元素的下标$i$就可以了，如果需要使用对应的元素，直接$T[i]$就可以获取。

• 单调栈里元素是递增呢？ 还是递减呢？

  • 递增栈就是求右边第一个比自己大的元素，从栈头（元素从栈头弹出）到栈底的顺序应该是从小到大的顺序。
  • 递减栈就是求右边第一个比自己小的元素，从栈头（元素从栈头弹出）到栈底的顺序应该是从大到小的顺序。

• 使用单调栈主要有三个判断条件：

  • 当前遍历的元素$T[i]$小于栈顶元素$T[st.top()]$的情况
  • 当前遍历的元素$T[i]$等于栈顶元素$T[st.top()]$的情况
  • 当前遍历的元素$T[i]$大于栈顶元素$T[st.top()]$的情况

单调栈工作过程？

• 从左向右依次遍历数组， 在每次循环中，若栈为空（第一次循环开始时），则直接将当前位置入栈；若栈非空，判断栈顶位置对应的元素是否大于等于当前位置的元素，将大于等于当前元素的位置依次出栈，直到栈为空，或者栈顶位置对应的元素小于当前元素，再将当前位置入栈 。

739. 每日温度

暴力解法（超时）

暴力解法就是两层遍历，时间复杂度为$O(n^2)$，空间复杂度$O(1)$

class Solution {
public:
    vector<int> dailyTemperatures(vector<int>& temperatures) {
        vector<int> ans(temperatures.size());
        ans[temperatures.size() - 1] = 0;   					//最后一天肯定是0
        for(int i = 1; i < temperatures.size(); i++){			//后一天大于前一天，直接是1
            if(temperatures[i] > temperatures[i - 1]){
                ans[i - 1] = 1; 
            }else{
                for(int j = i; j < temperatures.size(); j++){
                    if(temperatures[j] > temperatures[i - 1]){	//依次遍历
                        ans[i - 1] = j - i + 1;					
                        break;									
                    }
                }
            }
        }
        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

单调栈解法

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

496. 下一个更大元素 I

在 739. 每日温度 中是求每个元素下一个比当前元素大的元素的位置。

本题则是 $nums1$ 是 $nums2$的子集，找$nums1$中的元素在$nums2$中下一个比当前元素大的元素。

注意题目中说是两个没有重复元素 的数组 $nums1$ 和 $nums2$。

没有重复元素就可以用map来做映射了。根据数值快速找到下标，还可以判断$nums2[i]$是否在$nums1$中出现过。

遍历顺序：栈头到栈底的顺序，要从小到大，也就是保持栈里的元素为递增顺序。只要保持递增，才能找到右边第一个比自己大的元素。

• 情况一：当前遍历的元素$T[i]$小于栈顶元素$T[st.top()]$的情况，此时满足递增栈（栈头到栈底的顺序），所以直接入栈。

• 情况二：当前遍历的元素$T[i]$等于栈顶元素$T[st.top()]$的情况，直接入栈，因为要求的是右边第一个比自己大的元素，而不是大于等于。

• 情况三：当前遍历的元素$T[i]$大于栈顶元素$T[st.top()]$的情况，此时如果入栈就不满足递增栈了，这也是找到右边第一个比自己大的元素的时候。

  • 判断栈顶元素是否在$nums1$里出现过，（注意栈里的元素是$nums2$的元素），如果出现过，开始记录结果。
  • 此时栈顶元素在$nums2$中右面第一个大的元素是$nums2[i]$即当前遍历元素。

class Solution {
public:
    vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {
        stack<int> st;
        vector<int> result(nums1.size(), -1);
        if(nums1.size()== 0) return result;
        unordered_map<int, int> umap;     
                    // key - 元素 value - 下标
        for(int i = 0; i < nums1.size(); i++){
            umap[nums1[i]] = i;
        }
        st.push(0);
        for(int i = 1; i < nums2.size(); i++){
            while(!st.empty() && nums2[i] > nums2[st.top()]){
                if(umap.count(nums2[st.top()]) > 0){    
                    // 看map里是否存在这个元素
                    int index = umap[nums2[st.top()]];
                    // 找到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

503. 下一个更大元素 II

两个$nums$数组拼接在一起，使用单调栈计算出每一个元素的下一个最大值，最后再把结果集即$result$数组$resize$到原数组大小就可以了。

class Solution {
public:
    vector<int> nextGreaterElements(vector<int>& nums) {
        vector<int> nums1(nums.begin(),nums.end());
        nums.insert(nums.end(),nums1.begin(),nums1.end());
        vector<int> result(nums.size(), -1);
        if(nums.size() == 0) return result;
        stack<int> st;
        st.push(0);
        for(int i = 1; i < nums.size(); i++){
            while(!st.empty() && nums[i] > nums[st.top()]){
                result[st.top()] = nums[i];
                st.pop();
            }
            st.push(i);
        }
        result.resize(nums.size() / 2);
        return result;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

实际上，上述方案做了很多无用操作，例如修改了$nums$数组，而且最后还要把$result$数组$resize$回去。$resize$倒是不费时间，是$O(1)$的操作，但扩充$nums$数组相当于多了一个$O(n)$的操作。其实也可以不扩充$nums$，而是在遍历的过程中模拟走两次$nums$，代码如下：

class Solution {
public:
    vector<int> nextGreaterElements(vector<int>& nums) {
        vector<int> result(nums.size(),-1);
        if(nums.size() == 0) return result;
        stack<int> st;
        st.push(0);
        for(int i = 1; i < nums.size() * 2; i++){
            while(!st.empty() && nums[i % nums.size()] > nums[st.top()]){
                 // 模拟遍历两边nums，注意：都是用i % nums.size()来操作
                result[st.top()] = nums[i % nums.size()];
                st.pop();
            }
            st.push(i % nums.size());
        }
        return result;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

42. 接雨水

暴力解法（超时）

需要注意的是，要明确且统一按照行来计算，还是按照列来计算。

每一列雨水的高度，取决于，该列 左侧最高的柱子 和 右侧最高的柱子 中 矮的柱子的高度。$min(lHeight,rHeight)-height$

从头遍历一遍所有的列，然后求出每一列雨水的体积，相加之后就是总雨水的体积。（要注意第一个柱子和最后一个柱子不接雨水）。

class Solution {
public:
    int trap(vector<int>& height) {
        int sum = 0;
        for (int i = 0; i < height.size(); i++) {
            // 第一个柱子和最后一个柱子不接雨水
            if (i == 0 || i == height.size() - 1) continue;

            int rHeight = height[i]; // 记录右边柱子的最高高度
            int lHeight = height[i]; // 记录左边柱子的最高高度
            for (int r = i + 1; r < height.size(); r++) {
                if (height[r] > rHeight) rHeight = height[r];
            }
            for (int l = i - 1; l >= 0; l--) {
                if (height[l] > lHeight) lHeight = height[l];
            }
            int h = min(lHeight, rHeight) - height[i];
            if (h > 0) sum += h;
        }
        return sum;
    }
};
//超时，此方法实际上需要对每个下标位置都向两边扫描，时间复杂度为O(n^2)比较高。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

双指针法

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-GFEdBOLE-1658246682550)(C:\Users\Nothingserious\AppData\Roaming\Typora\typora-user-images\image-20220719225005571.png)]

class Solution {
public:
    int trap(vector<int>& height) {
        if(height.size() == 0) return 0;
        int left = 0, right = height.size() - 1;
        int maxleft = height[0], maxright = height[height.size()-1];
        int ans = 0;
        while (left <= right){
            maxleft = max(height[left],maxleft);
            maxright = max(height[right],maxright);
            if(maxleft < maxright){
                ans += maxleft - height[left];
                left++;
            }else{
                ans += maxright - height[right];
                right--;
            }
        }
        return ans;
    }
}
//时间复杂度：O(n)
//空间复杂度：O(1)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

动态规划

在暴力解法中为了得到两边的最高高度，每个柱子都向两边遍历，是有重复计算的。如果把每一个位置的左边最高高度记录在一个数组上（$maxLeft$），右边最高高度记录在一个数组上（$maxRight$），就能够避免重复计算，用到了动态规划。当前位置左边的最高高度是前一个位置的左边最高高度和本高度的最大值。即递推公式为：

从左向右遍历：$maxLeft[i]=max(height[i],maxLeft[i-1]);$

从右向左遍历：$maxRight[i]=max(height[i],maxRight[i+1]);$

class Solution {
public:
    int trap(vector<int>& height) {
        if(height.size() <= 2) return 0;
        vector<int> maxLeft(height.size(),0);
        vector<int> maxRight(height.size(),0);
        maxLeft[0] = height[0];
        for(int i = 1;i < height.size(); i++){
            maxLeft[i] = max(height[i], maxLeft[i-1]);
        }
        maxRight[height.size()-1] = height[height.size()-1];
        for(int i = height.size() - 2;i >= 0; i--){
            maxRight[i] = max(height[i], maxRight[i+1]);
        }
        int sum = 0;
        for(int i = 0; i < height.size(); i++){
            int count = min(maxLeft[i], maxRight[i]) - height[i];
            if(count > 0) sum += count;
        }
        return sum;
    }
};
//时间复杂度：O(n)
//空间复杂度：O(n)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

单调栈法

如果当前遍历的元素（柱子）高度小于栈顶元素的高度，就把这个元素加入栈中，因为栈里本来就要保持从小到大的顺序（从栈头到栈底）。

如果当前遍历的元素（柱子）高度等于栈顶元素的高度，要跟更新栈顶元素，因为遇到相相同高度的柱子，需要使用最右边的柱子来计算宽度。

如果当前遍历的元素（柱子）高度大于栈顶元素的高度，此时就出现凹槽了：

• 雨水高度是 $min(凹槽左边高度,凹槽右边高度)-凹槽底部高度$，代码为：int h = min(height[stk.top()], height[i]) - height[top];
• 雨水的宽度是 $凹槽右边的下标-凹槽左边的下标-1（因为只求中间宽度）$，代码为：int w = i - stk.top() - 1;
• 当前凹槽雨水的体积就是：h * w。

class Solution {
public:
    int trap(vector<int>& height) {
        int ans = 0;
        stack<int> stk;
        stk.push(0);
        for (int i = 1; i < height.size(); ++i) {
            while (!stk.empty() && height[i] > height[stk.top()]) {
                int top = stk.top();
                stk.pop();
                if (!stk.empty()) {
                    int w = i - stk.top() - 1;
                    int h = min(height[stk.top()], height[i]) - height[top];
                    ans += w * h;
                }
            }
            stk.push(i);
        }
        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

84. 柱状图中最大的矩形

暴力解法（超时）

可以枚举以每个柱形为高度的最大矩形的面积。具体来说是：依次遍历柱形的高度，对于每一个高度分别向两边扩散，求出以当前高度为矩形的最大宽度多少。对于每一个位置，都这样操作，得到一个矩形面积，求出最大值。

class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        int sum = 0;
        for (int i = 0; i < heights.size(); i++) {
            int left = i;
            int right = i;
            for (; left >= 0; left--) {
                if (heights[left] < heights[i]) break;
            }
            for (; right < heights.size(); right++) {
                if (heights[right] < heights[i]) break;
            }
            int w = right - left - 1;
            int h = heights[i];
            sum = max(sum, w * h);
        }
        return sum;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

时间复杂度：$O(N^2)$
空间复杂度：$O(1)$

动态规划

class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        vector<int> minLeftIndex(heights.size());
        vector<int> minRightIndex(heights.size());

        // 记录每个柱子 左边第一个小于该柱子的下标
        minLeftIndex[0] = -1; // 注意初始化，防止while死循环
        for (int i = 1; i < heights.size(); i++) {
            int t = i - 1;
            // 不断向左寻找的过程
            while (t >= 0 && heights[t] >= heights[i]){ 
                //如果大于的话，则继续排查（找左边第一个小于heights[t]的下标，也就是minLeftIndex[t]）
                t = minLeftIndex[t];
            }
            minLeftIndex[i] = t;    //记录柱子左边第一个小于该柱子的下标
        }
        // 记录每个柱子 右边第一个小于该柱子的下标
        minRightIndex[heights.size() - 1] = heights.size(); // 注意初始化，防止while死循环
        for (int i = heights.size() - 2; i >= 0; i--) {
            int t = i + 1;
            // 不断向右寻找的过程
            while (t < heights.size() && heights[t] >= heights[i]){
                t = minRightIndex[t];
            } 
            minRightIndex[i] = t;
        }
        // 求和
        int result = 0;
        for (int i = 0; i < heights.size(); i++) {
            int sum = heights[i] * (minRightIndex[i] - minLeftIndex[i] - 1);
            result = max(sum, result);
        }
        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
29
30
31
32
33
34
35
36

单调栈法

42. 接雨水是找每个柱子左右两边第一个大于该柱子高度的柱子，而本题是找每个柱子左右两边第一个小于该柱子的柱子。这里就涉及到了单调栈很重要的性质：单调栈的顺序。本题单调栈的顺序正好与接雨水反过来。只有栈里从大到小的顺序，才能保证栈顶元素找到左右两边第一个小于栈顶元素的柱子。

除了栈内元素顺序和接雨水不同，剩下的逻辑就都差不多了。栈顶和栈顶的下一个元素以及要入栈的三个元素组成了我们要求最大面积的高度和宽度。

• 情况一：当前遍历的元素$heights[i]$小于栈顶元素$heights[st.top()]$的情况
• 情况二：当前遍历的元素$heights[i]$等于栈顶元素$heights[st.top()]$的情况
• 情况三：当前遍历的元素$heights[i]$大于栈顶元素$heights[st.top()]$的情况

class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        stack<int> st;
        heights.insert(heights.begin(), 0);
        heights.push_back(0);   //数组头部和尾部加元素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, w * h);
           }
           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