题目描述
给定一个长度为N的整数数列,输出每个数左边第一个比它小的数,如果不存在则输出-1。
输入格式
第一行包含整数N,表示数列长度。
第二行包含N个整数,表示整数数列。
输出格式
共一行,包含N个整数,其中第i个数表示第i个数的左边第一个比它小的数,如果不存在则输出-1。
数据范围
1≤N≤$10^5$
1≤数列中元素≤$10^9$
所有操作保证合法。
输入样例
5
3 4 2 7 5
输出样例
-1 3 -1 2 2
思路
1.输入当前数后如果当前栈不空,并且栈顶元素>=当前数,则此栈顶元素不会被用到,弹出栈顶元素
2.若栈不空,输出栈顶元素;否则返回-1
3.将此元素压入栈中
C++ 代码
#include<cmath>
#include<cstdio>
#include<string>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;
const int N=100010;
int stk[N],tt;
int main(){
int m;
cin>>m;
for(int i=0;i<m;i++){
int x;
cin>>x;
while(tt && stk[tt]>=x) tt--;//当栈不空且栈顶元素>=当前数时,这个栈顶元素在后面检索其他数时被当前数代替,所以删去
if(tt) cout<<stk[tt]<<" ";
else cout<<"-1 ";
stk[++tt]=x;
}
return 0;
}