单调栈
Mine_King
2020-01-07 15:20:17
单调栈,就是一个栈,不过栈内元素保证单调性。即,栈内元素要么从小到大,要么从大到小。
而单调栈维护的就是一个数前/后第一个大于/小于他的数。
例题:[P5788 【模板】单调栈](https://www.luogu.com.cn/problem/P5788)
例题就是一个求每个数后第一个大于他的数。
那么重点来了:怎么做!面对这样的数据,不好下手。那么我们把她转化一下:有$n$个人,每个人向右看,求她看到的第一个人。
看图:
![](https://i.loli.net/2020/01/07/8LB6ZW5qg7m9y1c.png)
通过观察,我们会发现,在她后面的,比她矮的,一定会被她遮住。那么,这个点就没用了。而根据现实生活和刚才的推断,我们看到的人肯定是一个比一个高的,而没看到的,留着也没用,直接扔了QwQ。那么,这就是符合单调性的。再看,那些没用的人什么时候扔掉?当然是遇到比她高的人了。那么就可以一个一个地走掉,而且肯定是在已经判断过的人的前面(中间和后面的在之前就走掉了),所以就直接从前面弹出。咦?这不就像一个栈吗?没错,这就是单调栈的实现方法。
再归纳一下:
- 从后往前扫
- 对于每个点:
- 弹出栈顶比她小的元素
- 此时栈顶就是答案
- 加入这个元素
由于是从前往后输出,还要把答案放到一个数组里。
放代码:
```cpp
#include<cstdio>
#include<stack>
using namespace std;
int n,a[3000005],f[3000005];//a是需要判断的数组(即输入的数组),f是存储答案的数组
stack<int>s;//模拟用的栈
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
for(int i=n;i>=1;i--)
{
while(!s.empty()&&a[s.top()]<=a[i]) s.pop();//弹出栈顶比当前数小的
f[i]=s.empty()?0:s.top();//存储答案,由于没有比她大的要输出0,所以加了个三目运算
s.push(i);//压入当前元素
}
for(int i=1;i<=n;i++) printf("%d ",f[i]);//输出
return 0;
}
```
[完 结 辣!](https://www.luogu.com.cn/blog/yhdhg1395754790/)