/*
构造单调栈
对于当前元素,若栈顶元素大于当前元素,则弹出栈顶,
直至找到小于当前元素的位置,然后将当前元素入栈
所以栈内元素从栈顶到栈底一定是递减的
对于输出每个数左边第一个比它小的数这个问题:
大于当前元素的栈顶元素弹出?
因为当前元素比栈顶元素要更小,所以当寻找左边第一个小的元素时,当前元素更加有利
且栈顶元素之后不会用到
*/
C++ 代码
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+10;
int main(){
int n;
cin >> n;
int x;
int st[N],tt = 0;
for(int i = 0;i<n;i++){
cin >> x;
while(tt && st[tt] >= x) tt--;
//当栈顶元素大于当前元素 栈顶元素出栈 栈顶元素永远不会用到
if(tt) cout<<st[tt]<<" ";
else cout<<"-1 ";
st[++tt] = x;
}
return 0;
}