AcWing 830. 单调栈
原题链接
简单
作者:
风起于浮萍之末
,
2024-01-28 14:55:32
,
所有人可见
,
阅读 36
#include <iostream>
#include<algorithm>
using namespace std;
const int N = 100010;
int stk[N], tt;
int n;
// 加入我的左边比我大,那么他的左边就可以被删除
// 因为我是从右向左侧找
int main(){
cin.tie(0);
ios::sync_with_stdio(false);
cin >> n;
for(int i=0;i<n;i++){
int x;
cin>>x;
while(tt&&stk[tt]>=x) tt--;// tt是先保证栈不空 如果空就输出-1
// skt[tt]>=x 如果栈顶元素大于当前这个元素,说明栈顶元素永远不会被用到
// 因为我的下标比你大 同时我的值小于等于你
if(tt) cout<<stk[tt]<<" "; // 不空
else cout<<-1<<" ";//空
stk[++tt] =x;
}
return 0;
}