暴力做法O(N*N)

#include<bits/stdc++.h>
using namespace std;
int st[100100],a[101001],tp=0;
int main()
{
    int n;
    cin>>n;
    for(int i=0;i<n;i++)cin>>a[i];
    for(int i=0;i<n;i++)
    {
        if(i==0){cout<<-1<<" ";continue;}
        int flag=0;
        for(int j=i;j>=0;j--)
        {
            if(a[i]>a[j])
            {
                cout<<a[j]<<" ";
                flag=1;
                break;
            }
        }
        if(flag==0)
        {
            cout<<-1<<" ";
        }
    }
}

分析

以上是O(N*N)的时间复杂度，这道题N=1e5,整体复杂度也就是1e10一定会TLE

所以需要优化
要优化先看看能不能发现给的数据里的单调性

比如说输入样例：
5
3 4 1 2 5
题目说找这个数a[i]左边的一个比他小的数
比如现在走到i=2(下标从0开始)a[2]=1;
如果1这个数字在这一轮循环3 4就永远不会被当作最小值输出
以为1再3 4 的左边，由此就发现了单调性
只要在插入数据的时候发现他前一个数比他大或者等于他那么前一个数就直接弹出就行了
弹啊弹，直到发现他左边的数比他小，这个数就放在这里

他一直再跟他左边的数进行比较，弹出也是他左边的数，所以从一个方向进从一个方向出
这就是栈吗!。

以为每个数的左边都比他小，所以这就找到了单调性了吗

每次遍历的答案是啥

根据单调栈的性质
再当前元素未入栈的情况下第一个比他小的数就是栈顶元素

算法步骤

1.遍历原数组里的每个点

2.遍历到第i个点的时候只要i左边的点比i这个点的值要大，每个比他大的点都出栈（为保持原有的单调性）

3.输出栈顶元素

4.把第i个点加入队列

C++ 代码

blablablazhan

单调栈优化

时间复杂度O(N)

C++ 代码

#include<bits/stdc++.h>
using namespace std;
int st[100100],a[101001],tp=0;
int main()
{
    int n;
    cin>>n;
    for(int i=0;i<n;i++)cin>>a[i];
    for(int i=0;i<n;i++)
    {
        while(tp!=0&&st[tp-1]>=a[i])tp--;//注意等于也要出栈
        if(tp==0)cout<<-1<<" ";//因为左边没有元素
        else cout<<st[tp-1]<<" ";//输出栈顶元素
        st[tp++]=a[i];//当前元素入栈
    }
}