单调栈

单调栈与普通栈的区别

同样作为一种FILO (后进先出)的数据结构, 单调栈在普通栈的基础上增加了一个要求: 栈内元素必须严格单调递增或单调递减
栈顶到栈底严格递增的栈叫单调递增栈, 栈顶到栈底严格递减的栈叫单调递减栈

单调栈原理

元素进栈 (以单调递增栈为例):
\(e\) 是一个待进栈的元素, 从栈顶到栈底遍历元素, 直到栈为空或找到第一个比 \(e\) 大的元素才能让 \(e\) 进栈

由于一共只需操作 \(n\) 个元素, 所以时间复杂度为 \(O(n)\)

实现

模板: 后面第一个大于

题面

有一个长度为 \(n (1\leq n\leq 30000)\) 的序列 \(a (30\leq a_i\leq 100)\) , 对于每个 \(i\) , 求最小的 \(j\) 满足 \(i+j<=n\) 且\(a_{i+j}>a_i\), 如果没有则输出 \(0\)

输入样例

8 73 74 75 71 69 72 76 73

输出样例

1 1 4 2 1 1 0 0

思路

倒着遍历, 用单调递减栈维护序列, 插入时不断弹出小于等于当前数的, 直到发现第一个大于的再进栈。时间复杂度 \(O(n)\)
(如果是正着遍历那么每个数的答案都将为0)

code

#include<bits/stdc++.h>
using namespace std;
const int N=30010;
int a[N],n,res[N];
stack<int>st;
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++) scanf("%d",&a[i]);
	for(int i=n;i>=1;i--){
		while(!st.empty()&&a[st.top()]<=a[i]) st.pop();
		if(st.empty()) res[i]=0;
		else res[i]=st.top()-i;
		st.push(i);
	}
	for(int i=1;i<=n;i++) printf("%d ",res[i]);
	return 0;
}