AcWing 830. 单调栈
原题链接
简单
作者:
qing123
,
2021-02-07 15:34:26
,
所有人可见
,
阅读 255
单调栈,在输入元素的时候维护单调性
#include<iostream>
using namespace std;
const int N=1e5+10;
int q[N];//存放数据的模拟栈空间
int sp;//栈顶指针
void Init()
{
sp=-1;
}
//入栈
void push(int x)
{
sp++;
q[sp]=x;
}
//出栈
void pop()
{
sp--;
}
//判断栈是否空
bool empty()
{
if(sp==-1)return true;
else return false;
}
//查询栈顶元素
int query()
{
if(!empty())//非空时
{
return q[sp];
}
}
int main()
{
int m;
cin>>m;//操作次数
Init();
while(m--)
{
int x;//输入值
cin>>x;
if(empty())
{
cout<<"-1 ";//栈空
}
else{
//比较栈顶元素
//查栈顶
while(query()>=x)
{
pop();//出栈
}
if(empty())cout<<"-1 ";//栈空
else cout<<query()<<' ';
}
push(x);
}
}