【模板】 单调栈

传送门

题意

给定一个长度为(N)的整数数列，输出每个数(A_{i})左边第一个比它小的数，如果不存在则输出(-1)。

数据范围

(1leq Nleq 10^{5})
(1leq A_{i} leq 10^{9})

题解

• 每次入栈的时候将栈中所有大于它的全部出栈

• 对于当前的数大于它的一定不会是左边第一个小于它的数

• 对于当前数后面输入的数字，比它大的显然没有它更靠近后面的不会被考虑

Code

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for(int i=a;i<n;i++)
const int N=1e5+10;
int n;
int stk[N],cnt;

int main()
{
    scanf("%d",&n);
    rep(i,0,n)
    {
        int x;scanf("%d",&x);
        while(cnt && stk[cnt] >=x) cnt--;
        if(cnt) printf("%d ",stk[cnt]);
        else printf("-1 ");
        stk[++cnt]=x;
    }
}