找邻居

找邻居

给定一个长度为 \(N\) 的整数数列， 输出每个数左边距离最近的且比它小的数， 如果不存在则输出 -1。

输入格式

第1行一个整数$ N（1 ≤ N ≤ 3× 10^6）$

第2行有$ N \(个整数，\) 1≤a_i≤10^9$

输出格式

共一行， 包含$ N$ 个整数， 其中第$ i$ 个数表示第$ i $个数的左边距离最近的比它小的数， 如果不存在则输出 -1

样例

输入样例

5
3 4 2 7 5

输出样例

-1 3 -1 2 2

数据范围

对于 100% 的数据，$ 1≤N≤3×10^6$, \(1≤\)数列中元素\(≤10^9\)

解析

维护一个单调递增栈

#include<iostream>
using namespace std;
const int N=3e6+10;
int n,m,a[N],st[N];

int main(){
    scanf("%d", &n);
    for(int i=1; i<=n; i++)scanf("%d", &a[i]);
    int hh=0; a[0]=-1;
    for(int i=1; i<=n; i++){
        while(hh&& a[st[hh]] >= a[i]) --hh;
        printf("%d ", a[st[hh]]);
        st[++hh] = i;
    }
    return 0;
}