个人笔记
给定一个长度为 $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;
}