贴上很喜欢的一张图

img

单调栈

单调队列主要用于 O(n) 解决滑动窗口问题，单调栈则主要用于 O(n) 解决NGE问题（Next Greater Element）

也就是，对序列中每个元素，找到下一个比它大的元素。（当然，“下一个”可以换成“上一个”，“比它大”也可以换成“比他小”，原理不变。）

这比单调队列还简单一点。我们维护一个栈，表示“待确定NGE的元素”，然后遍历序列。当我们碰上一个新元素，我们知道，越靠近栈顶的元素离新元素位置越近。所以不断比较新元素与栈顶，如果新元素比栈顶大，则可断定新元素就是栈顶的NGE，于是弹出栈顶并继续比较。直到新元素不比栈顶大，再将新元素压入栈。显然，这样形成的栈是单调递减的。

如果是对数列中的每个元素，寻找其左侧第一个比它大的元素位置。当某个元素被从栈内弹出时，代表它遇到了一个比它更大的元素，因为是从右往左遍历，所以该元素就是第一个比它大的元素，即所求。

【模板】单调栈

题目背景

模板题，无背景。

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

输入格式

第一行一个正整数 \(n\)。

第二行 \(n\) 个正整数 \(a_{1\dots n}\)。

输出格式

一行 \(n\) 个整数表示 \(f(1), f(2), \dots, f(n)\) 的值。

样例 #1

样例输入 #1

1
2
5
1 4 2 3 5

样例输出 #1

1
2 5 4 5 0

提示

【数据规模与约定】

对于 \(30\%\) 的数据，\(n\leq 100\)；

对于 \(60\%\) 的数据，\(n\leq 5 \times 10^3\) ；

对于 \(100\%\) 的数据，\(1 \le n\leq 3\times 10^6\)，\(1\leq a_i\leq 10^9\)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for(int i=a;i<=n;i++)
int n;
const int N=5e6;
int a[N];
int stk[N];
int ans[N];
int main()
{
cin>>n;
int top=0;
rep(i,1,n)
{
	cin>>a[i];
while(top && !(a[stk[top]]>=a[i]))	
ans[stk[top--]]=i;
	stk[++top]=i;
}
//构造一个单调递减栈
rep(i,1,n)
{
	cout<<ans[i]<<' ';
}

}