单调栈
作用:在$$O(n)$$时间复杂度获得一个序列中每个元素左边或右边第一个比它小的数或比它大的数。
#include <bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int a[N];
int stk[N],tt=0;
int main()
{
int n;
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i];
for(int i=1;i<=n;i++)
{
while(tt && stk[tt]>=a[i]) tt--;
if(tt<=0) printf("-1 ");
else printf("%d ", stk[tt]);
stk[++tt]=a[i];
}
return 0;
}