个人笔记

给定一个长度为 $N$ 的整数数列，输出每个数左边第一个比它小的数，如果不存在则输出 $-1$。

输入格式

第一行包含整数 $N$，表示数列长度。

第二行包含 $N$ 个整数，表示整数数列。

输出格式

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

数据范围

$1 \le N \le 10^5$
$1 \le 数列中元素 \le 10^9$

输入样例：

5
3 4 2 7 5

输出样例：

-1 3 -1 2 2

思路

对于当前数字$x$，用一个栈存$x$左边所有比它小的数，并保证其单调性，这样输出时输出栈顶元素即可，如果栈为空，则为没有比$x$小的数

代码

#include <iostream>

using namespace std;

const int N = 1e5 + 10;

int stack[N], top;
int n;

int main() {
    cin >> n;

    while (n --) {
        int x;
        cin >> x;
        while (top && stack[top] >= x) top --;
        if (top) cout << stack[top] << ' ';
        else cout << "-1" << ' ';
        stack[++ top] = x;
    }

    return 0;
}