单调栈学习笔记
以洛谷 P5788 【模板】单调栈 为例。
题目描述 - 单调栈的基本作用
题目很简单：给定一个数列，求每一个数往后看第一个比它大的数是谁。
我们来看样例：
1
2
5
1 4 2 3 5
显而易见，对于第一个数字 1 ，第一个比它大的数字是 4 ，排在第二位；对于第二个数字 4 ，第一个比它大的数字是 5 ，排在第五位……以此类推。
深入理解单调栈
下面让我们把数据可视化。
首先迈出关键一步：因为题目中要求的是向右边看第一个比当前高的，也就是说已知信息应该在当前的右边。所以我们要以从右向左的顺序来寻找规律。否则，本题将难以解决。
我们先来看最后一个 5 。因为这是我们第一个看的，其右边没有更多信息了，所以按题目输出为 0 。
看完 5 ，往左一个看到 3 。由于 3 比 5 小，所以输出为 5 （这是真实 5 的位置）。同理， 2 的输出为 4 （这是真实 3 的位置）。
现在我们已经看了 2, 3, 5 ，也就是数字 4 的后面有 2, 3, 5。现在看到了数字 4 。我们发现 4 往后看一个是 2 ，然而 $4 > 2$ ，所以 2 不是我们要找的数，丢掉；丢掉了 2 ，看到 3 ，由于 $4 > 3$ ，所以 3 也不是要找的数，丢掉；终于看到了 5 ，由于 $4 < 5$ ，所以 5 就是我们要找的数了。
让我们来思考最后一个数字 1 。显然，它的对应数就是 4 。如果把 1 改成 7 呢？如图：
由于我们已经丢掉了 4 后面所有小于 4 的数字，所以这些被丢掉的数字一定也小于 7 ，我们不用操心这些数字里是否有我们可能要寻找的数字。那么，我们再次进行“丢掉”操作，现在 7 后面的数字有 4, 5 （ 2, 3 已经被 4 丢掉了），而 4, 5 都小于 7 ，所以 4, 5 都被丢掉了，剩下了一个‘空’，所以 7 的答案变成了 0 。
让我们来重新审视一下整个过程：
- 从右往左看，如果后面的数字有比当前的数字小的，就丢掉；
- 丢到剩下面对的第一个比当前的大为止，这个数就是满足要求的。
这样一看，这似乎就是一个栈的操作，而且这个栈中的元素是单调递增或递减的。我们就将其称作单调栈。
来看看 OI-wiki 上对单调栈的定义：
顾名思义，单调栈即满足单调性的栈结构。与单调队列相比，其只在一端进行进出。
代码实现
读入完后，我们需要：
- 从右往左看：
1
for(int i=n;i>=1;i--)
- 弹出栈中所有小于等于当前元素的：
1 2 3
while(!s.empty()&&a[i]>=a[s.top()]){ s.pop(); }
- 获得当前答案：
1
ans[i]=(s.empty()?0:s.top());
- 将当前元素压入栈中：
1
s.push(i);
注意：输入输出应该使用 scanf ，否则会超时。
Full Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <bits/stdc++.h>
using namespace std;
const int maxn=3e6+10;
int n;
int a[maxn];
int ans[maxn];
stack <int> s;
int main(){
cin>>n;
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
}
for(int i=n;i>=1;i--){
while(!s.empty()&&a[i]>=a[s.top()]){
s.pop();
}
ans[i]=(s.empty()?0:s.top());
s.push(i);
}
for(int i=1;i<=n;i++){
printf("%d ",ans[i]);
}
return 0;
}