单调栈合集

单调栈模板

• 单调栈分为单调递增栈和单调递减栈

1. 单调递增栈即栈内元素保持单调递增的栈
2. 同理单调递减栈即栈内元素保持单调递减的栈

• 操作规则（下面都以单调递增栈为例）

1. 如果新的元素比栈顶元素大，就入栈
2. 如果新的元素较小，那就一直把栈内元素弹出来，直到栈顶比新元素小

• 加入这样一个规则之后，会有什么效果

1. 栈内的元素是递增的
2. 当元素出栈时，说明新元素是出栈元素向后找第一个比其小的元素
3. 当元素出栈后，说明新栈顶元素是出栈元素向前找第一个比其小的元素

• C++模板

stack<int> st;
for(int i = 0; i < nums.size(); i++){
	while(!st.empty() && st.top() > nums[i]){
		st.pop();
	}
	st.push(nums[i]);
}

496. 下一个更大元素 I

nums1 中数字 x 的 下一个更大元素 是指 x 在 nums2 中对应位置 右侧 的 第一个 比 x 大的元素。

给你两个 没有重复元素 的数组 nums1 和 nums2 ，下标从 0 开始计数，其中nums1 是 nums2 的子集。

对于每个 0 <= i < nums1.length ，找出满足 nums1[i] == nums2[j] 的下标 j ，并且在 nums2 确定 nums2[j] 的 下一个更大元素 。如果不存在下一个更大元素，那么本次查询的答案是 -1 。

返回一个长度为 nums1.length 的数组 ans 作为答案，满足 ans[i] 是如上所述的 下一个更大元素 。

示例 1：

输入：nums1 = [4,1,2], nums2 = [1,3,4,2].
输出：[-1,3,-1]
解释：nums1 中每个值的下一个更大元素如下所述：
- 4 ，用加粗斜体标识，nums2 = [1,3,4,2]。不存在下一个更大元素，所以答案是 -1 。
- 1 ，用加粗斜体标识，nums2 = [1,3,4,2]。下一个更大元素是 3 。
- 2 ，用加粗斜体标识，nums2 = [1,3,4,2]。不存在下一个更大元素，所以答案是 -1 。

示例 2：

输入：nums1 = [2,4], nums2 = [1,2,3,4].
输出：[3,-1]
解释：nums1 中每个值的下一个更大元素如下所述：
- 2 ，用加粗斜体标识，nums2 = [1,2,3,4]。下一个更大元素是 3 。
- 4 ，用加粗斜体标识，nums2 = [1,2,3,4]。不存在下一个更大元素，所以答案是 -1 。

提示：

• 1 <= nums1.length <= nums2.length <= 1000
• 0 <= nums1[i], nums2[i] <= 104
• nums1和nums2中所有整数 互不相同
• nums1 中的所有整数同样出现在 nums2 中

C++

class Solution {
public:
    vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {
        map<int, int> mp; // <nums1中该元素值, 对应在nums2中的下一个最大元素值>
        stack<int> stk;
        for(int i = 0; i < nums2.size(); i ++){
            while(!stk.empty() && nums2[i] > stk.top()){    // 栈非空
                int top = stk.top();
                stk.pop();
                mp[top] = nums2[i]; 
            } 
            stk.push(nums2[i]);
        }

        for(int i = 0; i < nums1.size(); i++){
            nums1[i] = mp[nums1[i]] ? mp[nums1[i]] : -1;
        }
        return nums1;
    }
};

503. 下一个更大元素 II

给定一个循环数组 nums （ nums[nums.length - 1] 的下一个元素是 nums[0] ），返回 nums 中每个元素的 下一个更大元素 。

数字 x 的 下一个更大的元素 是按数组遍历顺序，这个数字之后的第一个比它更大的数，这意味着你应该循环地搜索它的下一个更大的数。如果不存在，则输出 -1 。

示例 1:

输入: nums = [1,2,1]
输出: [2,-1,2]
解释: 第一个 1 的下一个更大的数是 2；
数字 2 找不到下一个更大的数； 
第二个 1 的下一个最大的数需要循环搜索，结果也是 2。

示例 2:

输入: nums = [1,2,3,4,3]
输出: [2,3,4,-1,4]

提示:

• 1 <= nums.length <= 104
• -109 <= nums[i] <= 109

C++

class Solution {
public:
    vector<int> nextGreaterElements(vector<int>& nums) {
        stack<int> stk; // 元素下标
        map<int, int> mp; // 该数组元素下标 -> 对应下一个最大元素值
        for(int i = 0; i < 2 * nums.size() - 1; i ++){
            while(!stk.empty() && nums[i % nums.size()] > nums[stk.top()]){
                int top = stk.top();
                stk.pop();
                mp[top] = nums[i % nums.size()];
            }
            stk.push(i % nums.size());
        }

        for(int i = 0; i < nums.size(); i ++){
            nums[i] = mp.find(i) != mp.end() ? mp[i] : -1;
        }
        return nums;
    }
};

739. 每日温度

给定一个整数数组 temperatures ，表示每天的温度，返回一个数组 answer ，其中 answer[i] 是指对于第 i 天，下一个更高温度出现在几天后。如果气温在这之后都不会升高，请在该位置用 0 来代替。

示例 1:

输入: temperatures = [73,74,75,71,69,72,76,73]
输出: [1,1,4,2,1,1,0,0]

示例 2:

输入: temperatures = [30,40,50,60]
输出: [1,1,1,0]

示例 3:

输入: temperatures = [30,60,90]
输出: [1,1,0]

提示：

• 1 <= temperatures.length <= 105
• 30 <= temperatures[i] <= 100

C++

class Solution {
public:
    vector<int> dailyTemperatures(vector<int>& temperatures) {
        stack<int> stk; // 下标
        map<int, int> mp; // <当前下标, 长度>
        for(int i = 0; i < temperatures.size(); i ++){
            while(!stk.empty() && temperatures[i] > temperatures[stk.top()]){
                int L = i - stk.top();
                int top = stk.top();
                mp[top] = L;
                stk.pop();
            }
            stk.push(i);
        }

        for(int i = 0; i < temperatures.size(); i ++){
            if(mp.find(i) != mp.end()){
                temperatures[i] = mp[i];
            }
            else temperatures[i] = 0;
        }
        
        return temperatures;
    }
};

402. 移掉 K 位数字

给你一个以字符串表示的非负整数 num 和一个整数 k ，移除这个数中的 k 位数字，使得剩下的数字最小。请你以字符串形式返回这个最小的数字。

示例 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 。

提示：

• 1 <= k <= num.length <= 105
• num 仅由若干位数字（0 - 9）组成
• 除了 0 本身之外，num 不含任何前导零

C++

class Solution {
public:
    string removeKdigits(string num, int k) {
        string res;
        int n = num.size();
        bool isLeadingZero = true;
        stack<int> stk; //存下标
        if(n == 1) return k == 1 ? "0" : num;
        
        for(int i = 0; i < n; i ++){
            while(!stk.empty() && num[i] - '0' < num[stk.top()] - '0' && k > 0){
                k --;
                stk.pop();
            }
            stk.push(i);      
        }
        
        while(k > 0) { // 之前k没用完,代表后面有多余的数 不然最后一个数没办法处理
            k--;
            stk.pop();
        }

        while(!stk.empty()){
            res += num[stk.top()];
            stk.pop();
        }
        reverse(res.begin(), res.end());

        for(int i = 0; i < res.size(); i ++){
            while(isLeadingZero && res[i] == '0') res.erase(i,1);
            isLeadingZero = false;
        }
        
        return res.size() ? res : "0";      
    }
};


// 数组模拟栈 时空复杂度更小
// class Solution {
// public:
//     string removeKdigits(string num, int k) {
//         vector<char> stk;
//         for (auto& digit: num) {
//             while (stk.size() > 0 && stk.back() > digit && k) {
//                 stk.pop_back();
//                 k -= 1;
//             }
//             stk.push_back(digit);
//         }

//         for (; k > 0; --k) {
//             stk.pop_back();
//         }

//         string ans = "";
//         bool isLeadingZero = true;
//         for (auto& digit: stk) {
//             if (isLeadingZero && digit == '0') {
//                 continue;
//             }
//             isLeadingZero = false;
//             ans += digit;
//         }
//         return ans == "" ? "0" : ans;
//     }
// };

901. 股票价格跨度

设计一个算法收集某些股票的每日报价，并返回该股票当日价格的 跨度 。

当日股票价格的 跨度 被定义为股票价格小于或等于今天价格的最大连续日数（从今天开始往回数，包括今天）。

• 例如，如果未来 7 天股票的价格是 [100,80,60,70,60,75,85]，那么股票跨度将是 [1,1,1,2,1,4,6] 。

实现 StockSpanner 类：

• StockSpanner() 初始化类对象。
• int next(int price) 给出今天的股价 price ，返回该股票当日价格的 跨度 。

示例：

输入：
["StockSpanner", "next", "next", "next", "next", "next", "next", "next"]
[[], [100], [80], [60], [70], [60], [75], [85]]
输出：
[null, 1, 1, 1, 2, 1, 4, 6]

解释：
StockSpanner stockSpanner = new StockSpanner();
stockSpanner.next(100); // 返回 1
stockSpanner.next(80);  // 返回 1
stockSpanner.next(60);  // 返回 1
stockSpanner.next(70);  // 返回 2
stockSpanner.next(60);  // 返回 1
stockSpanner.next(75);  // 返回 4 ，因为截至今天的最后 4 个股价 (包括今天的股价 75) 都小于或等于今天的股价。
stockSpanner.next(85);  // 返回 6

提示：

• 1 <= price <= 105
• 最多调用 next 方法 104 次

C++

class StockSpanner {
public:
    StockSpanner() {
        
    }
    
    int next(int price) {
        int res = 1;
        while(!stk.empty() && price >= stk.top().first){ // 新加入的price >= 栈顶的price
            res += stk.top().second; 
            stk.pop();
        }
        stk.push(pair<int, int>(price, res)); // 前面没有小于等于price的 , 就只有它自己
        return res;
    }

private:
    stack<pair<int, int>> stk;
};

/**
 * Your StockSpanner object will be instantiated and called as such:
 * StockSpanner* obj = new StockSpanner();
 * int param_1 = obj->next(price);
 */

581. 最短无序连续子数组

给你一个整数数组 nums ，你需要找出一个 连续子数组 ，如果对这个子数组进行升序排序，那么整个数组都会变为升序排序。

请你找出符合题意的 最短 子数组，并输出它的长度。

示例 1：

输入：nums = [2,6,4,8,10,9,15]
输出：5
解释：你只需要对 [6, 4, 8, 10, 9] 进行升序排序，那么整个表都会变为升序排序。

示例 2：

输入：nums = [1,2,3,4]
输出：0

示例 3：

输入：nums = [1]
输出：0

提示：

• 1 <= nums.length <= 104
• -105 <= nums[i] <= 105

C++

class Solution {
public:
    int findUnsortedSubarray(vector<int>& nums) {
        /* 单调栈(vector模拟)*/
        int n = nums.size();
        int l = n - 1, r = 0;
        vector<int> stk;
        //从左往右递增栈，找到不符合自己位置的最小元素的坐标
        for (int i = 0; i < n; i++) { 
            while (stk.size() && nums[stk.back()] > nums[i]) {
                l = min(l, stk.back());
                stk.pop_back();
            }
            stk.push_back(i);
        }
        stk.clear();
        //从右往左递减栈，找到不符合自己位置的最大元素的坐标
        for (int i = n - 1; i >= 0; i--) {
            while (stk.size() && nums[stk.back()] < nums[i]) {
                r = max(r, stk.back());
                stk.pop_back();
            }
            stk.push_back(i);
        }
        //r - l > 0时所需排序长度为r - l + 1， r - l <= 0时整体已经有序
        return r - l > 0 ? r - l + 1 : 0;
    }
};

42. 接雨水

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

示例 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
• 1 <= n <= 2 * 104
• 0 <= height[i] <= 105

C++

• 单调栈

// 我们用栈保存每堵墙。

// 当遍历墙的高度的时候，如果当前高度小于栈顶的墙高度，说明这里会有积水，我们将墙的高度的下标入栈。

// 如果当前高度大于栈顶的墙的高度，说明之前的积水到这里停下，我们可以计算下有多少积水了。计算完，就把当前的墙继续入栈，作为新的积水的墙。

// 总体的原则就是，

// 当前高度小于等于栈顶高度，入栈，指针后移。

// 当前高度大于栈顶高度，出栈，计算出当前墙和栈顶的墙之间水的多少，然后计算当前的高度和新栈的高度的关系，重复第 2 步。直到当前墙的高度不大于栈顶高度或者栈空，然后把当前墙入栈，指针后移。

class Solution {
public:
    int trap(vector<int>& height) {
        int ans = 0;
        stack<int> stk;
        int n = height.size();
        for (int i = 0; i < n; ++i) {
            while (!stk.empty() && height[i] > height[stk.top()]) {
                int top = stk.top();
                stk.pop();
                if (stk.empty()) {
                    break;
                }
                int left = stk.top();
                int currWidth = i - left - 1;
                int currHeight = min(height[left], height[i]) - height[top];
                ans += currWidth * currHeight;
            }
            stk.push(i);
        }
        return ans;
    }
};

• 动态规划

class Solution {
public:
    int res = 0;
    // 找到每一列左边最高的墙和右边最高的墙
    int trap(vector<int>& height) {
        int n = height.size();
        vector<vector<int>> dp(n, vector<int>(2, 0));
        // dp[0][0] = 0; 左边最高的墙
        // dp[n - 1][1] = 0; 右边最高的墙
        for(int i = n - 2; i >= 0; i --){
            dp[i][1] = max(dp[i + 1][1], height[i + 1]);
        }
        for(int i = 1; i < n; i ++){
            dp[n - i - 1][1] = max(dp[n - i][1], height[n - i]);
            dp[i][0] = max(dp[i - 1][0], height[i - 1]);
            res += min(dp[i][0], dp[i][1]) > height[i] ? min(dp[i][0], dp[i][1]) - height[i] : 0;
        }
        return res;
    }
};

84. 柱状图中最大的矩形

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

求在该柱状图中，能够勾勒出来的矩形的最大面积。

示例 1:

输入：heights = [2,1,5,6,2,3]
输出：10
解释：最大的矩形为图中红色区域，面积为 10

示例 2：

输入： heights = [2,4]
输出： 4

提示：

• 1 <= heights.length <=105
• 0 <= heights[i] <= 104

C++

// 对于一个高度，如果能得到向左和向右的边界
// 那么就能对每个高度求一次面积
// 遍历所有高度，即可得出最大面积
// 使用单调栈，在出栈操作时得到前后边界并计算面积
class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
      int res = 0;
      stack<int> s;
      heights.insert(heights.begin(), 0);  // 若没在前加0，不能保证stack不为空，所以left的值就需要赋初始值0
      heights.push_back(0);

      for(int i = 0; i < heights.size(); i ++){
        while(!s.empty() && heights[i] < heights[s.top()]){  // 2进栈 6，5被弹出
            //6: cur = 4; left = 4; right = 4; (right - left + 1) = 1
            //5: cur = 3; left = 3; right = 4; (right - left + 1) = 2
            int cur = s.top();
            s.pop();
            int left = s.top() + 1;
            int right = i - 1; 
            res = max(res, (right - left + 1) * heights[cur]);
        }
        s.push(i);
      }
      return res;
    }
};