LeetCode 单调栈专题

男娘i 2022-11-19 04:24 94阅读 0赞

### [84. 柱状图中最大的矩形][84.] ###

给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。

求在该柱状图中，能够勾勒出来的矩形的最大面积。  
![在这里插入图片描述][2021041415484182.png]  
以上是柱状图的示例，其中每个柱子的宽度为 1，给定的高度为 \[2,1,5,6,2,3\]。

![在这里插入图片描述][20210414154847540.png]  
图中阴影部分为所能勾勒出的最大矩形面积，其面积为 10 个单位。

示例:

> 输入: \[2,1,5,6,2,3\]  
> 输出: 10

*  第一种解法：**暴力**（超时）。我们可以遍历每个柱子，求得以当前柱子高度的最大面积矩形，以当前柱子开始，从左扫描，从右扫描，直到遇到低于当前柱子高度停下，然后计算面积。时间复杂度为O(n^2)

int largestRectangleArea(vector<int>& heights) {
        
            // 暴力解法：遍历每个柱子，求得以当前柱子高度的最大面积矩形
            int res = 0;
            int n = heights.size();
            for(int i=0; i<n; ++i){
        
                int cur_height = heights[i];
                int l = i - 1, r = i + 1;
                // 向左走
                while(l >= 0){
        
                    if(heights[l] < cur_height){
        
                        break;
                    }
                    l--;
                }
                // 向右走
                while(r < n){
        
                    if(heights[r] < cur_height){
        
                        break;
                    }
                    r++;
                }
                res = max(res, cur_height * (r - l - 1));
            }
            return res;
        }

*  **单调栈**。  
    题解：https://leetcode-cn.com/problems/largest-rectangle-in-histogram/solution/bao-li-jie-fa-zhan-by-liweiwei1419/

int largestRectangleArea(vector<int>& heights) {
        
            int res = 0;
            heights.insert(heights.begin(), 0);
            heights.push_back(0);
            stack<int> st; // 单调栈存取下标
            for(int i=0; i<heights.size(); ++i){
        
                while(!st.empty() && heights[st.top()] > heights[i]){
        
                    int length = heights[st.top()];
                    st.pop();
                    int left = st.top() + 1;
                    int right = i - 1;
                    res = max(res, length * (right - left + 1));
                }
                st.push(i);
            }
            return res;
        }

### [42. 接雨水][42.] ###

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。

![在这里插入图片描述][20210420144140185.png]

示例 1：

> 输入：height = \[0,1,0,2,1,0,1,3,2,1,2,1\]  
> 输出：6  
> 解释：上面是由数组 \[0,1,0,2,1,0,1,3,2,1,2,1\] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。

示例 2：

> 输入：height = \[4,2,0,3,2,5\]  
> 输出：9

提示：

n == height.length  
0 <= n <= 3 \* 104  
0 <= height\[i\] <= 105

*  **按行求**。  
    从1到max(height)依次求每一行能接的雨水数量，这里能接的雨水数量就是左右都存在比当前行高度大的高度时。

class Solution {
        
    public:
        int trap(vector<int>& height) {
        
            // 按行求（超时）
            int sum = 0;
            int max_height = 0;
            for(int i=0; i<height.size(); ++i){
        
                max_height = max(max_height, height[i]);
            }
            for(int i=1; i<=max_height; ++i){
        
                bool isUpdate = false;
                int temp = 0;
                for(int j=0; j<height.size(); ++j){
        
                    if(isUpdate && height[j] < i){
        
                        temp++;
                    }
                    if(height[j] >= i){
        
                        isUpdate = true;
                        sum += temp;
                        temp = 0;
                    }
                }
            }
            return sum;
        }
    };

*  **按列求**  
    从第2列到倒数第二列依次求（第1列和最后一列没意义），求得当前列左右方向上最高高度，如果这两个最高高度的较小值大于当前列高度，则可以求得当前列能接到的雨水高度。

class Solution {
        
    public:
        int trap(vector<int>& height) {
        
             // 按列求
            if(height.size()==0) return 0;
            int res = 0;
            for(int i=1; i<height.size()-1; ++i){
        
                int max_left = 0;
                for(int j=i-1; j>=0; --j){
        
                    max_left = max(height[j], max_left);
                }
    
                int max_right = 0;
                for(int j=i+1; j<height.size(); ++j){
        
                    max_right = max(height[j], max_right);
                }
    
                int minm = min(max_left, max_right);
                if(minm > height[i]){
        
                    res += (minm - height[i]);
                }
            }
            return res;
        }
    };

*  **动态规划**  
    因为我们需要求得每列的左右方向最高高度，我们可以直接通过两次动态规划来求得每列左右方向上的最高高度，这样就不需要每次都要遍历找。

class Solution {
        
    public:
        int trap(vector<int>& height) {
        
            if(height.size()==0 || height.size()==1) return 0;
            int n = height.size();
            int res = 0;
            vector<int> dp_l(n, 0), dp_r(n, 0);
            dp_l[1] = height[0]; 
            dp_r[n-2] = height[n-1];
            for(int i=2; i<n-1; ++i){
        
                if(height[i-1] > dp_l[i-1]){
        
                    dp_l[i] = height[i-1];
                }
                else{
        
                    dp_l[i] = dp_l[i-1];
                }
            }
            for(int i=n-3; i>=1; --i){
        
                if(height[i+1] > dp_r[i+1]){
        
                    dp_r[i] = height[i+1];
                }
                else{
        
                    dp_r[i] = dp_r[i+1];
                }
            }
    
            for(int i=1; i<n-1; ++i){
        
                int minm = min(dp_l[i], dp_r[i]);
                if(minm > height[i]){
        
                    res += (minm - height[i]);
                }
            }
            return res;
        }
    };

*  **单调栈**  
    分析一下，如果当前高度高于之前的高度，说明可能接到雨水，因此我们使用单调递减栈来存放下标

int res = 0;
     stack<int> stk; // 单调减栈，存放下标
     for(int i=0; i<height.size(); ++i){
        
         while(!stk.empty() && height[stk.top()] < height[i]){
        
             int h = height[stk.top()];
             stk.pop();
             if (stk.empty()) {
         // 栈空就出去，说明左边不可能存在墙来堵，也就不会有雨水能接到
                 break; 
             }
             int distance = i - stk.top() - 1; //两堵墙之前的距离。
             int minn = min(height[stk.top()], height[i]);
             res += distance * (minn - h);
         }
         stk.push(i);
     }
     return res;

### [739. 每日温度][739.] ###

请根据每日 气温 列表，重新生成一个列表。对应位置的输出为：要想观测到更高的气温，至少需要等待的天数。如果气温在这之后都不会升高，请在该位置用 0 来代替。

例如，给定一个列表 temperatures = \[73, 74, 75, 71, 69, 72, 76, 73\]，你的输出应该是 \[1, 1, 4, 2, 1, 1, 0, 0\]。

提示：气温 列表长度的范围是 \[1, 30000\]。每个气温的值的均为华氏度，都是在 \[30, 100\] 范围内的整数。  
依然采用  
**单调栈** 的方法求解。我们发现遇到更高的温度，需要等待的天数才会更新，否则为0，因此可以采用单调递减栈。

class Solution {
        
    public:
        vector<int> dailyTemperatures(vector<int>& T) {
        
            vector<int> res(T.size(), 0);
            stack<int> stk; // 单调栈，存放下标
            stk.push(0);
            for(int i=1; i<T.size(); ++i){
        
                while(!stk.empty() && T[stk.top()] < T[i]){
        
                    res[stk.top()] = i - stk.top();
                    stk.pop();
                }
                stk.push(i);
            }
            return res;
        }
    };

### [496. 下一个更大元素 I][496. _ I] ###

给你两个 没有重复元素 的数组 nums1 和 nums2 ，其中nums1 是 nums2 的子集。

请你找出 nums1 中每个元素在 nums2 中的下一个比其大的值。

nums1 中数字 x 的下一个更大元素是指 x 在 nums2 中对应位置的右边的第一个比 x 大的元素。如果不存在，对应位置输出 -1 。

示例 1:

> 输入: nums1 = \[4,1,2\], nums2 = \[1,3,4,2\].  
> 输出: \[-1,3,-1\]  
> 解释:  
> 对于 num1 中的数字 4 ，你无法在第二个数组中找到下一个更大的数字，因此输出 -1 。  
> 对于 num1 中的数字 1 ，第二个数组中数字1右边的下一个较大数字是 3 。  
> 对于 num1 中的数字 2 ，第二个数组中没有下一个更大的数字，因此输出 -1 。

同上，当我们需要找到更高的元素，我们需要用一个单调递减栈来保存递减元素的下标。

因为nums1是nums2的子集，所以我们首先对nums2中每个元素找到其更高的元素，使用hash表进行保存，最后再遍历nums1，如果hash中没有则-1，否则就是hash\[nums1\[i\]\]

class Solution {
        
    public:
        vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {
        
            vector<int> res(nums1.size(), -1);
            stack<int> stk; // 单调减栈
            map<int, int> hash;
            for(int i=0; i<nums2.size(); ++i){
        
                while(!stk.empty() && nums2[stk.top()] < nums2[i]){
        
                    hash[nums2[stk.top()]] = nums2[i]; 
                    stk.pop();
                }
                stk.push(i);
            }
            for(int i=0; i<nums1.size(); ++i){
        
                auto it = hash.find(nums1[i]);
                res[i] = it == hash.end()?-1:hash[nums1[i]];
            }
            return res;
        }
    };

### [316. 去除重复字母][316.] ###

给你一个字符串 s ，请你去除字符串中重复的字母，使得每个字母只出现一次。需保证 返回结果的字典序最小（要求不能打乱其他字符的相对位置）。

示例 1：

> 输入：s = “bcabc”  
> 输出：“abc”

示例 2：

> 输入：s = “cbacdcbc”  
> 输出：“acdb”

### [901. 股票价格跨度][901.] ###

### [402. 移掉K位数字][402. _K] ###

给定一个以字符串表示的非负整数 num，移除这个数中的 k 位数字，使得剩下的数字最小。

注意:

num 的长度小于 10002 且 ≥ k。  
num 不会包含任何前导零。

举个例子：  
对于 num = “1432219”, k = 3，  
我们首先选择"1"，然后选择"4"，因为"4">“1”，所以不删除"1"，然后选择"3"，我们发现"3" < “4”，因此删除"4"，选择"3"，然后选择"2"，我们发现"2" < “3”，因此删除"3"，选择"2"，依次往下直到删除了3个数字。因此这是一个递增栈。

class Solution {
        
    public:
        string removeKdigits(string num, int k) {
        
            string res = "";
            stack<char> stk;
            for(int i=0; i<num.length(); ++i){
        
                while(k && !stk.empty() && stk.top()>(num[i])){
        
                    k--;
                    stk.pop();
                }
                stk.push(num[i]);
            }
            for(; k>0; --k){
        
                stk.pop();
            }
            while(!stk.empty()){
        
                res += stk.top();
                stk.pop();
            }
            reverse(res.begin(), res.end());
            int i = 0;
            while(i < res.length() && res[i]=='0'){
        
                i++;
            }
            if(i == res.length()) return "0";
            else return res.substr(i, res.length() - i);
        }
    };

示例 1 :

> 输入: num = “1432219”, k = 3  
> 输出: “1219”  
> 解释: 移除掉三个数字 4, 3, 和 2 形成一个新的最小的数字 1219。

示例 2 :

> 输入: num = “10200”, k = 1  
> 输出: “200”  
> 解释: 移掉首位的 1 剩下的数字为 200. 注意输出不能有任何前导零。

示例 3 :

> 输入: num = “10”, k = 2  
> 输出: “0”  
> 解释: 从原数字移除所有的数字，剩余为空就是 0。

### [581. 最短无序连续子数组][581.] ###

[84.]: https://leetcode-cn.com/problems/largest-rectangle-in-histogram
[2021041415484182.png]: /images/20221022/988acc0706d44aa3999405e1807cb2f5.png
[20210414154847540.png]: /images/20221022/c6daab8a8cc541ff911d9dc558c3c528.png
[42.]: https://leetcode-cn.com/problems/trapping-rain-water/
[20210420144140185.png]: /images/20221022/ab22018fe21e43a7a1127f0da2e983f2.png
[739.]: https://leetcode-cn.com/problems/daily-temperatures/
[496. _ I]: https://leetcode-cn.com/problems/next-greater-element-i/
[316.]: https://leetcode-cn.com/problems/remove-duplicate-letters/
[901.]: https://leetcode-cn.com/problems/online-stock-span/
[402. _K]: https://leetcode-cn.com/problems/remove-k-digits/
[581.]: https://leetcode-cn.com/problems/shortest-unsorted-continuous-subarray/