题目分析

充分利用新输入元素与原栈顶元素的关系来降低时间复杂度

相关代码

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

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

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;
}