AcWing 830. 单调栈
原题链接
简单
作者:
云_580
,
2024-09-05 12:33:07
,
所有人可见
,
阅读 1
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+10;
int n,top;
int st[N],q[N],ans[N];
//数组模拟栈
void push(int x){
st[top++]=x;
}
void pop(){
top--;
}
bool empty(){
return top==0;
}
int query(){
return st[top-1];
}
int main(){
cin>>n;
for(int i = 1;i<=n;i++)cin>>q[i];
for(int i = n;i>=1;i--){
if(i==n)push(i);//如果i==n直接压入栈即可
else{
//当栈不为空,并且q[i]是比q[query()]小的时候
//说明是左边第一个比它小的数,更新答案ans[query()]即可
//并弹出栈顶元素,因为之后都不会用到这个元素了
//从右往左枚举
while(!empty()&&q[i]<q[query()]){
ans[query()]=q[i];
pop();
}
push(i);
}
}
for(int i = 1;i<=n;i++){
if(!ans[i])cout<<-1<<" ";
else cout<<ans[i]<<" ";
}
return 0;
}