题解 P5788 【【模板】单调栈】

发表于 | 阅读次数：
本文字数： 5.1k | 阅读时长 ≈ 5 分钟

前言

单调栈的模板题目，本人是手写单调栈。

单调栈

首先了解一下什么是单调栈吧！

单调栈就是使栈内元素单调递增或者单调递减的栈，单调栈也只能在栈顶操作。

我们先来模拟一遍吧！

做一个比喻，比方说：有个集训队招人，一个数代表了一个选手的能力值，先进来的选手年龄会比较大，后面的选手年龄比较小，但是这个集训队没有人数限制，那么如果遇到一个比你小还比你强的人那么准备退役吧。

比如有 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

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 <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 洛谷的，自己的，记得来玩哦！

谢谢观赏！

-------- 本文结束 感谢阅读 --------