题目分析

直接利用单调栈思想
对于A[i],stk中只存储排在A[i]之前且比A[i]小的元素 且按照升序存储

相关代码实现

#include<bits/stdc++.h>
using namespace std;

const int N=100010;
int stk[N];
int tt=-1;

//直接利用单调栈思想
//对于A[i],stk中只存储排在A[i]之前且比A[i]小的元素 且按照升序存储
int main(){
    int n;
    cin>>n;
    int pos=-1;
    for(int i=0;i<n;i++){
        int x;
        cin>>x;
        while(tt>=0&&stk[tt]>=x) tt--;
        if(tt==-1) cout<<"-1 ";
        else cout<<stk[tt]<<" ";
        stk[++tt]=x;
    }
    return 0;
}


/*
int main(){
    int n;
    cin>>n;
    int pos=-1;
    for(int i=0;i<n;i++){
        int x;
        cin>>x;

        //比较新输入元素x与栈顶元素的关系 从而降低时间复杂度
        //栈为空 输出-1
        //x大于栈顶元素 输出栈顶元素
        //x与栈顶元素相等 输出上次输出的值
        if(tt==-1) cout<<"-1 ";
        else if(x>stk[tt]) cout<<stk[tt]<<" ";
             else if(x==stk[tt]) cout<<pos<<" ";
                    else{
                    pos=tt;
                    while(pos!=-1&&stk[pos]>=x)  pos--;
                    if(pos!=-1) pos=stk[pos];
                    cout<<pos<<" ";
                    }
        stk[++tt]=x;
    }
    return 0;
}*/