思路

两个数组,一个存值,一个存对应位置的比他小的数的位置
当第 i - 1 个数比 i 小时,i左边第一个比 i 小的数的位置必然小于或者等于比 i - 1 小的数的位置
因此可以直接跳到 i - 1 的数对应位置重复上一个步骤判断
直至大于i

time: 90ms

看了前面几篇题解,这个应该是最快的

c++

#include<iostream>
using namespace std;

const int N = 100010;

int n;
int a[N],b[N];

int main()
{
        scanf("%d",&n);
        for(int i=1;i<=n;i++)
                scanf("%d",&a[i]);
        for(int i=1;i<=n;i++)
                for(int j=i-1;~(j-1)>>31;)
                {
                        if(a[j]<a[i])
                        {
                                b[i]=j;
                                break;
                        }
                        else j=b[j];
                }
        for(int i=1;i<=n;i++)
        {
                if(b[i]) printf("%d ",a[b[i]]);
                else printf("-1 ");
        }
        return 0;
}