蒟蒻求助单调栈模板
查看原帖
蒟蒻求助单调栈模板
340632
Cry_For_theMoon楼主2020/8/19 20:34

rt

我明明用了单调栈,还是4个点TLE了。

哪位大佬能告诉我哪里出错了

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<stack>
using namespace std;
const int MAXN=3e6+10;
stack<int>st;
int a[MAXN],ans[MAXN]; 
int n;
int main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	for(int i=n;i>=1;i--){
		while(!st.empty()){
			int crt=st.top();
			if(a[crt] <= a[i]){
				st.pop();
			}else{
				break;
			}
		} 
		if(!st.empty()){
			int crt=st.top();
			ans[i]=crt;
		}
		st.push(i);
	}
	for(int i=1;i<=n;i++){
		printf("%d ",ans[i]);
	}
	return 0;
}
2020/8/19 20:34
加载中...