题目描述

输出每个数左边比它小的第一个数

样例

输入：

5
3 4 2 7 5

输出：

-1 3 -1 2 2

算法：(单调栈)

AC代码

//有逆序的关系  前面的数就删掉了
#include <iostream>
using namespace std;
const int N =100010;
int stk[N],tt;
//tt栈顶指针
int main(){
    //ios::sync_with_stdio(false);
    int n;
    cin>>n;
    for(int i = 0; i < n;i++){
        int x;
        scanf("%d",&x);
        while(tt&&stk[tt]>=x) tt--;
        //栈里面的元素大于当前元素  栈顶元素就没希望了
        //如果 是找左边比他大的第一个数  那么栈顶元素比当前元素小 则没希望
        if(tt) printf("%d ",stk[tt]);
        else printf("-1 ");

        stk[++tt] = x;
    }
    return 0;
}