单调栈
在元素进栈的同时与已经进栈的元素比较,若比要进栈的元素大,则可以直接删去,因为不可能选这个进栈的元素当答案(因为要进栈的元素既比他近也比它小)有新加入的元素在就轮不到它上场
#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
#include<vector>
using namespace std;
const int N = 1e5 + 10;
int stk[N], tt;//栈顶指针
//初始化
void index()
{
tt = -1;
}
//进栈
void push(int x)
{
stk[++tt] = x;
}
//出栈
void pop()
{
tt--;
}
//判断是否为空
bool empty()
{
if (tt == -1)return true;
return false;
}
//访问栈顶元素
int query()
{
return stk[tt];
}
int main()
{
int n;
scanf("%d",&n);
index();
for (int i = 1; i <= n; i++)
{
int data;
scanf("%d",&data);
//如果栈不为空且栈顶元素大于data
while (empty() == 0 && query() >= data)
{
pop();
}
//如果不为空,则此时的栈顶为离插入的数最近的小于他的数
if (empty() == 0)printf("%d ",query());
//如果为空,则没有比它小的数,输出-1
else
printf("%d ",-1);
//将该点入栈
push(data);
}
return 0;
}