单调栈

单调栈是一种通过维护单调性用 $O(n)$ 的时间求解前面的数据对后面的数据没有影响的问题。

顾名思义，单调栈其实就是一个栈，手写和 STL 都可以。 写单调栈，首先要确定这个栈是要单调递增还是单调递减。

一个单调栈的模板题：求一个长度为 $n$ 的序列中每一个数的左边第一个比它小的数，如果没有，则输出 $0$。其中 $n\le 10^6$。 发现这个题目如果每一次暴力去查找的话，时间复杂度是 $O(n^2)$，显然不可以通过。 这个时候就要维护一个单调递增栈，每一次要放入数据时，就判断栈顶是否比该元素大，如果是，则一直弹栈，直到栈顶比该元素小。而此时的栈顶就一定是左边第一个比该元素大的数。最后把该元素入栈即可。 时间复杂度和空间复杂度都是 $O(n)$。

注意点 1.注意开始遍历数组之前，要往栈里放一个 $0$。 2.记得在判断栈顶单调性并弹栈时判断栈里面有数。

code

cpp
Copy
#include<bits/stdc++.h>
using namespace std;
const int N=3e6+10;
int a[N];
int s[N],top;
int n;
int main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	s[++top]=0;
	for(int i=1;i<=n;i++){
		while(top&&a[i]<=s[top])top--;
		cout<<s[top]<<' ';
		s[++top]=a[i];
	}
	return 0;
}