AcWing 830. 单调栈
原题链接
简单
作者:
Hope_
,
2021-06-08 22:00:49
,
所有人可见
,
阅读 230
单调栈
C++ 代码
#include<iostream>
using namespace std;
const int N=1e5+10;
int tt;//全局变量默认初始化为0 tt指向当前的元素
int stk[N];//stk为模拟栈 里面的内容为单调递增 这条性质由自己定义
int main(){
int m;
cin>>m;
//m次操作
while(m--){
int x;
cin>>x;//处理输入的数据 这样操作属于在线操作了
//第一个数据输出的一定是-1 因为前面没有比他小的
// 当前栈不为空 且比x大的就不要了 因为对于后面的元素来说 它只要前面第一个比他小的元素 这样前面比栈顶元素大的 都可以不要了
//如果碰到相等的也要删掉
while(tt&&stk[tt]>=x){
tt--;//弹出
}
//在while循环之外的 栈内都是递增的了 且都不会大于x了
//判断栈顶元素 然后输出数据
if(tt) cout<<stk[tt]<<" ";
else cout<<-1<<" ";
stk[++tt]=x;//存入栈中
}
return 0;
}