单调栈详解【C/C++】

 前言：了解过单调队列后，你会发现单调栈的思想其实挺简单...

当然前提是要了解一下什么是栈(stack)。

看待一个问题，从不同角度，也许能有不同的收获。

在数学家眼中，单调栈本质上是一个严格或非严格维护的单调递增或单调递减的数学结构。

其核心在于动态的维护动态递增或递减的有序关系。

而对于算法工程师，他们首先关注单调栈的核心优势：O(n)的时间复杂度。在需要遍历序列，并纪录极值的情况下（如接雨水、每日温度），暴力解法通常需要O(n^2)，而单调栈，通过每个元素仅入栈与出栈一次，将复杂度，降低至O(n)，这对于在大数据的场景下，具有决定性意义。

既然单调栈是一种思想，那必然衍生出了理论(一切操作基于stack)。

单调递增：从栈顶到栈底，保持递增。注意是从栈顶！

================
|6 5 4 3 2 1   <-栈顶
================

单调递减：从栈顶到栈底，保持递减。

================
|1 2 3 4 5 6   <-栈顶
================

而常见的题型：

• 下一个更大元素：维护递减栈，当新元素大于栈顶时，栈顶元素的下一个更大元素即为当前元素。
• 接雨水问题：通过双单调栈分别记录左右边界的最大高度，计算每个位置能接的雨水量。
• 股票买卖问题：利用单调栈追踪价格趋势，找到最佳买卖点。

接下来，用题目来实操！切记，单调栈内 存入下标更优。

大纲：

1、每日温度--单调栈的简单应用

2、接雨水--用单调栈实现贪心思想 && 能用双指针(对撞指针)替代

题目

1、每日温度

给定一个整数数组 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

class Solution {
// 如果暴力，时间复杂度为O(n^2)
// 利用其单调性
public:
    vector<int> dailyTemperatures(vector<int>& temperatures) {
        vector<int> res(temperatures.size());
        stack<int> st;
        for(int i=0; i<temperatures.size(); ++i){
            while(!st.empty()&&temperatures[st.top()]<temperatures[i]){
                res[st.top()]=i-st.top();
                st.pop();
            }
            st.push(i);
        }
        return res;
    }
};

2、接雨水

给定 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

解题思路：

首先申明一下，本题也能用双指针中的对撞指针解决。

本题巧妙运用单调栈的单调性质 并结合 贪心思想。

设置了一个单调递增栈。

如果有大于栈顶的元素进来了

那代表两个柱子之间可能存在洼地

这时，取栈顶的前两个元素

栈顶top、栈顶的下面的下个元素left。

为啥要取top呢，是为了获得水的最低点。

方便计算面积。

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

借鉴博客：

1、关于单调栈（Monotone Stack）的详细讲解

2、【算法】一文带你弄懂单调栈！