• 单调栈
  • 例题

单调栈

单调的栈，即插入元素时保证栈内元素是有序的。

例题

1. P2422 良好的感觉
   贪心，其实对每一个最小值，找到其的左右小于最大范围，但关键在于怎么快速找到这个范围，这里利用了单调栈
   详见代码：

const int maxm=1e5+5,inf=0x3f3f3f3f,mod=998244353;
ll n,a[maxm],sum[maxm],f[maxm];
stack<ll> m;

void solve(){
	cin>>n;
	ll ans=0;
	a[0]=0;
	for(int i=1;i<=n;++i){
		cin>>a[i];
	}
	a[++n]=0;//用于最后将所有清空
	for(int i=1;i<=n;++i){
		sum[i]=sum[i-1]+a[i];
		while(!m.empty()&&a[m.top()]>a[i]){
			f[m.top()]+=sum[i-1]-sum[m.top()];//统计到右边第一个小的
			m.pop();
		}
		if(!m.empty())//统计到左边第一个小的
			f[i]+=sum[i]-sum[m.top()];
		else f[i]+=sum[i];
		m.push(i);
	}
	for(int i=1;i<=n;++i)
		ans=max(ans,f[i]*a[i]);//计算每个点作为最小时的结果
	cout<<ans<<'\n';
	return ;
}

signed main(){
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	int _=1;
	// cin>>_;
	while(_--){
		solve();
	}
	return 0;
}

2. P5788 【模板】单调栈
   见代码模板：

const int maxm=3e6+5,inf=0x3f3f3f3f,mod=998244353;
int n,a[maxm],ans[maxm];

void solve(){
	cin>>n;
	for(int i=1;i<=n;++i){
		cin>>a[i];
	}
	stack<int> q;
	for(int i=n;i>0;--i){
		while(!q.empty()&&a[q.top()]<=a[i]){//注意等号！！！
			q.pop();
		}
		if(q.empty()) ans[i]=0;
		else ans[i]=q.top();
		q.push(i);
	}
	for(int i=1;i<=n;++i){
		cout<<ans[i]<<" \n"[i==n];
	}
	return ;
}

signed main(){
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	int _=1;
//	cin>>_;
	while(_--){
		solve();
	}
	return 0;
}