P5788 【模板】单调栈

【模板】单调栈

题目背景

模板题，无背景。

2019.12.12 更新数据，放宽时限，现在不再卡常了。

题目描述

给出项数为 n 的整数数列 a_{1 ... n}。

定义函数 f(i) 代表数列中第 i 个元素之后第一个大于 a_i 的元素的下标，即 f(i)=min_i<j≤ n, a_j > a_i{j}。若不存在，则 f(i)=0。

试求出 f(1... n)。

输入格式

第一行一个正整数 n。

第二行 n 个正整数 a_{1 ... n}。

输出格式

一行 n 个整数 f(1... n) 的值。

样例 #1

样例输入 #1

5
1 4 2 3 5

样例输出 #1

2 5 4 5 0

提示

【数据规模与约定】

对于 30% 的数据，n≤ 100；

对于 60% 的数据，n≤ 5 × 10^3 ；

对于 100% 的数据，1 ≤ n≤ 3× 10^6，1≤ a_i≤ 10^9。

分析

单调栈，就是一个栈，不过栈内元素保证单调性。即，栈内元素要么从小到大，要么从大到小。
而单调栈维护的就是一个数前/后第一个大于/小于他的数。

例题：P5788 【模板】单调栈
例题就是一个求每个数后第一个大于他的数。

那么重点来了：怎么做！面对这样的数据，不好下手。那么我们把她转化一下：有n个人，每个人向右看，求她看到的第一个人。
看图：

通过观察，我们会发现，在她后面的，比她矮的，一定会被她遮住。那么，这个点就没用了。而根据现实生活和刚才的推断，我们看到的人肯定是一个比一个高的，而没看到的，留着也没用，直接扔了QwQ。那么，这就是符合单调性的。再看，那些没用的人什么时候扔掉？当然是遇到比她高的人了。那么就可以一个一个地走掉，而且肯定是在已经判断过的人的前面（中间和后面的在之前就走掉了），所以就直接从前面弹出。咦？这不就像一个栈吗？没错，这就是单调栈的实现方法。

再归纳一下：

• 从后往前扫

• 对于每个点：

  • 弹出栈顶比她小的元素
  • 此时栈顶就是答案
  • 加入这个元素
    由于是从前往后输出，还要把答案放到一个数组里。

提交答案

#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;
}