题目描述 - 单调栈的基本作用#

题目很简单：给定一个数列，求每一个数往后看第一个比它大的数是谁。

我们来看样例：

1
5
2
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 。

让我们来重新审视一下整个过程：

1. 从右往左看，如果后面的数字有比当前的数字小的，就丢掉；
2. 丢到剩下面对的第一个比当前的大为止，这个数就是满足要求的。

这样一看，这似乎就是一个栈的操作，而且这个栈中的元素是单调递增或递减的。我们就将其称作单调栈。

来看看 OI-wiki 上对单调栈的定义：

顾名思义，单调栈即满足单调性的栈结构。与单调队列相比，其只在一端进行进出。

代码实现#

读入完后，我们需要：

1. 从右往左看：

1
for(int i=n;i>=1;i--)

2. 弹出栈中所有小于等于当前元素的：

1
while(!s.empty()&&a[i]>=a[s.top()]){
2
        s.pop();
3
}

3. 获得当前答案：

1
ans[i]=(s.empty()?0:s.top());

4. 将当前元素压入栈中：

1
s.push(i);

注意：输入输出应该使用 scanf ，否则会超时。

1
#include <bits/stdc++.h>
2
using namespace std;
3
const int maxn=3e6+10;
4
int n;
5
int a[maxn];
6
int ans[maxn];
7
stack <int> s;
8
int main(){
9
    cin>>n;
10
    for(int i=1;i<=n;i++){
11
        scanf("%d",&a[i]);
12
    }
13
    for(int i=n;i>=1;i--){
14
        while(!s.empty()&&a[i]>=a[s.top()]){
15
            s.pop();
16
        }
17
        ans[i]=(s.empty()?0:s.top());
18
        s.push(i);
19
    }
20
    for(int i=1;i<=n;i++){
21
        printf("%d ",ans[i]);
22
    }
23
    return 0;
24
}