给定一个长度为N的整数数列,输出每一个数左边第一个比它小的数,如果不存在则输出-1
采用单调栈的思想来做,核心思想是当前面被输入的元素比后面被输入的元素还大的时候,那么前面这个元素就可以抛弃不要了,因为后面被输入的这个更小的元素一定是优先被输出,因此采用一个栈来存储输入的数
每次输入一个数x,就将它和栈顶元素比较,如果栈顶元素比输入的元素要大则抛弃它一直抛弃到出现比输入元素小的数字,那么这个数字就是离输入元素最近且最小的数字,当然有可能一直弹到栈里没有元素,那么就输出-1表示没有比x小的数存在,最后把x输入到栈里面
#include <bits/stdc++.h>
using namespace std;
const int N = 1000;
int st[N], tt;
int main() {
int m;
cin >> m;
int x;
for (int i = 0; i < m; i++) {
cin >> x;
while (st[tt] >= x && tt)
tt--;//一直减减到没有第一个比x小的数,或者是没有
if (tt)
cout << st[tt] << " ";
else
cout << -1 << " ";
st[++tt] = x;
}
return 0;
}