题解 P5788 【【模板】单调栈】
cstdios
2020-02-23 15:51:18
## 前言
单调栈的模板题目,本人是手写单调栈。
## 单调栈
首先了解一下什么是单调栈吧!
单调栈就是使栈内元素单调递增或者单调递减的栈,单调栈也只能在栈顶操作。
我们先来模拟一遍吧!
做一个比喻,比方说:有个集训队招人,一个数代表了一个选手的能力值,先进来的选手年龄会比较大,后面的选手年龄比较小,但是这个集训队没有人数限制,那么如果遇到一个比你小还比你强的人那么准备退役吧。
比如有 5 个能力值分别是:
1 7 5 6 3
要加进来这个单调栈。
首先是 1 也就是 选手1 ,那么集训队没有人和他比较所以进入集训队。
单调栈的情况:1 。
然后是 7 也就是 选手2 ,那么我们可以发现,选手2 比 选手1 要小,并且 选手2 的能力比 选手1 要强,那么 选手1 留着也没啥用,淘汰!~~好残酷呀!~~
单调栈的情况:7 。
然后是 5 选手3 ,选手3 比 选手2 年龄要小,但是 选手3 的能力没有 选手2 强,那么 选手3 招进集训队。
单调栈的情况:7 5 。
那么接下来是 6 选手4 ,选手4 比 选手3 年龄要小,比他还要强, 选手3 淘汰!往后比较,发现 选手2 虽然比 选手4 要大,但是他能力很强!所以不会被淘汰,将 选手4 招进集训队。
单调栈的情况:7 6 。
最后是 3 选手5 ,选手5 比 选手4 要小,但是 选手4 的能力比 选手5 要强,所以 选手4 必定也比不过 选手2 ,但由于 选手5 小所以不淘汰他。
单调栈的情况:7 6 3 。
通过这个模拟我们发现,~~如果你很强,就算你年龄大也不会被淘汰~~,其实不是这样,在单调队列(比单调栈高级的东西)里面你就算再强也终究有时候会退役的,所以好好珍惜吧!
## 分析
刚刚解析完了单调栈,那么,现在开始分析一下这道题目吧!
这道题目就是说往右边看,找出第一个(能力)大于你的数(选手)。
不妨把它反过来,从最后一个开始入单调栈。
如果说没有比它小的那么就是输出 0 。
细节看代码吧!
## Code
```cpp
#include <iostream>
#include <cstdio>
#define INF 3000005
//头文件+预处理名。
using namespace std;
int n,a[Inf],q[INF],r,f[INF];
//定义变量,其中a数组表示输入的数,q数组表示存下标的单调栈,f数组是存结果。
int main() {
scanf("%d",&n);
for (int i=1; i<=n; i++) scanf("%d",&a[i]);
//上面是读入。
for (int i=n; i>=1; i--) {
//从最后开始枚举。
while (a[i]>=a[q[r]] && r>0) r--;
//如果说它找到了比矮高的人并且不是最后,那么将那个矮的人弹掉,毕竟后面也不会有人看到它了,因为如果看到它的话那么必定可以看到比它前面的还比它高的。
f[i]=q[r];
//存结果,因为要正向输出。
q[++r]=i;
//将它入栈。
}
for (int i=1; i<=n; i++) printf("%d ",f[i]);
//最后正着输出。
return 0;
}
```
## 写在后面的话
我这篇题解如果有错误,那么请在评论区里留言,我将会很感谢反映的人。
最后,宣传一下我的两个blog [洛谷的](https://www.luogu.com.cn/blog/dgt/solution-p5788),[自己的](https://cstdios.cf/uncategorized/solution-p5788/),记得来玩哦!
**谢谢观赏!**