单调栈

定义

单调栈，即一种栈内元素具有单调性的栈。

理解

单调栈内的元素从栈顶到栈底始终保持单调性（单调递增或单调递减），栈顶元素是所有栈内元素的一个最值（单调递增栈的栈顶元素是所有栈内元素的最小值，单调递减栈的栈顶元素是所有栈内元素的最大值）。

为了栈内元素的单调性，单调栈的插入操作涉及两个步骤：

  1. 将一个元素插入单调栈之前，需要「在保证将该元素插入到栈顶后整个栈满足单调性的前提下」弹出最少的元素。
  2. 待所有不满足单调性的元素都出栈后，将当前元素入栈。

代码模板

单调递增栈

1
2
3
4
5
6
7
8
9
stack<int> stk; // 单调递增栈（从栈顶到栈底单调递增）
int num; // 待入栈的元素

// 单调递增栈的插入操作
while(!stk.empty() && stk.top() <= num) stk.pop(); // 将不满足单调性的元素都出栈
stk.push(num); // 将当前元素入栈

// 单调递增栈中的最小值
int minn = stk.top();

单调递减栈

1
2
3
4
5
6
7
8
9
stack<int> stk; // 单调递减栈（从栈顶到栈底单调递减）
int num; // 待入栈的元素

// 单调递减栈的插入操作
while(!stk.empty() && stk.top() >= num) stk.pop(); // 将不满足单调性的元素都出栈
stk.push(num); // 将当前元素入栈

// 单调递减栈中的最大值
int maxx = stk.top();

具体应用

每日温度

给定一个数组 tt（下标从 00 开始），表示每天的气温。对于每一天的气温 tit_i，输出几天后气温会升高。
例如，如果下一个比 tit_i 更高的气温是 tjt_j（i<ji < j，并且 ti<tjt_i < t_j），那么输出 j−ij - i，说明 j−ij - i 天后气温会升高。
如果对于某一天 tit_i，气温在之后都不会再升高，那么输出 00。

对于每天的温度 tit_i，需要求出该天之后第一个比 tit_i 大的温度 tjt_j，并计算得到两者的距离 j−ij - i。
定义一个单调栈，从栈底到栈顶单调非递增。
遍历整个数组 tt，如果栈非空，且当前元素大于栈顶元素，如果直接插入当前元素会破坏栈的单调性，那么需要取出栈顶元素。由于当前元素大于栈顶元素，而且一定是第一个大于栈顶元素的数，直接求出下标差就是两者的距离。
然后，将栈顶元素出栈，继续看新的栈顶元素，并依次求出栈顶元素与当前元素的下标差作为答案。
最终，直到当前元素小于等于栈顶元素停止，再将当前元素入栈，这样就可以一直保持栈的单调性，且每个数字和第一个大于它的数的距离也可以算出来。
如果数组遍历完，栈中还有元素，则说明栈中剩余的元素都找不到在它之后第一个比它大的数，答案均为 00 即可。

对于温度数组 {9, 7, 4, 7, 12, 7}，算法运行过程如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
vector<int> t; // 温度数组
int n; // 温度数组的长度
stack<int> stk; // 单调栈（栈中记录元素的下标）
vector<int> ans(n); // 结果数组

for(int i = 0; i < n; i++){
    while(!stk.empty() && t[stk.top()] < t[i]){
        int tp = stk.top(); // 对于栈顶元素而言，其后第一个大于它的元素就是当前元素
        ans[tp] = i - tp; // 两者的下标差即为栈顶元素对应的答案
        stk.pop();
    }
    stk.push(i);
}

while(!stk.empty()){ // 数组遍历完，栈中还有元素，则说明栈中剩余的元素都找不到在它之后第一个比它大的数
    int tp = stk.top();
    stk.pop();
    ans[tp] = 0;
}