单调栈一些题目练习

最近发现单调栈不怎么会熟练使用,写点东西提醒下自己 第一题 给你一个数组 a i a_i ai​,问你对于一个长度为 i i i的连续区间,最大化该区间的最小值。你需要回答长度1~n的区间的答案并且输出他们。 对于这个问题,其实我已经遇过好几次了,这类问题需要关注的是谁作为最小值而造成的区间影响. 我们认为 a i ai ai就是当前区间的最小值,那么我们需要处理出当前该元素的最左边索引 l l l,最右索引 r r r,那么它就可以作为答案算入区间 r − l + 1 中 r-l+1中 r−l+1中. 对于处理出 l , r l,r l,r这两个值,这就是单调栈的作用了。 首先处理r数组,从前往后扫,如果碰到一个值 a i ai ai大于栈顶元素,取出栈顶所有元素,把他们的值 r [ j ] = i r[j]=i r[j]=i 再处理 l l l数组,从后边往前边扫,如果碰到一个元素大于当前 i i i,和 r r r一样的处理

#include
using namespace std;
const int maxn = 1e6+5;
const int INF = 1e9+7;
typedef long long ll;
typedef pair pii;
#define all(a) (a).begin(), (a).end()
#define pb(a) push_back(a)
vector G[maxn];
int a[maxn];int s[maxn];
int l[maxn],r[maxn],ans[maxn];
int main(){
    ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int n;cin>>n;
	for(int i=1;i>a[i];
	int top = 0;
	for(int i=1;i0&&a[s[top]]>a[i]){
			r[s[top]] =i-1;top--;
		}
		top++;
		s[top] = i;
	}
	while(top>0) r[s[top]] = n,top--;
	for(int i=n;i>=1;i--){
		while(top>0&&a[s[top]]>a[i]){
			l[s[top]] = i+1;top--;
		}
		top++;s[top]=i;
	}
	while(top>0) l[s[top]]=1,top--;
	for(int i=1;i