题目描述
给定一个长度为N的整数数列,输出每个数左边第一个比它小的数,如果不存在则输出-1。
输入格式
第一行包含整数N,表示数列长度。
第二行包含N个整数,表示整数数列。
输出格式
共一行,包含N个整数,其中第i个数表示第i个数的左边第一个比它小的数,如果不存在则输出-1。
数据范围
1≤N≤105
1≤数列中元素≤109
输入样例:
5
3 4 2 7 5
输出样例:
-1 3 -1 2 2
算法
单调栈
详情看代码注释,边看代码边看注释,方便理解。
参考文献
y总讲解视频
C++ 代码
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 100010;
//stk模拟的单调栈 tt栈顶
int stk[N] , tt;
//n个数据
int n ;
int main(){
cin>>n;
//输入n个数据
for(int i = 0 ; i < n ; i++){
//x具体的数据
int x;
cin>>x;
//当栈不为空并且栈顶元素大于等于当前值的时候,弹出
/*
因为我们要找的是当前值左边第一个比它小的数,而这个单调栈就是符合这
样一种性质:从栈底到栈顶都是单调增加的。如果说当前栈顶元素比当前值
都打,那说明此时的这个值必然是在后面输入进来的数中,比栈顶元素更加
靠近那个后来值。并且这个x比后来值小的概率也会比栈顶元素大。因为它
本来就比栈顶元素小,还在栈顶元素的右边。
综上,当此时栈顶元素大于等于此时输入的x值,那么栈顶元素弹出,x进栈
替换掉它。直到x找到适合它的位置,并再次构成单调栈。注意是while循环
*/
while(tt != 0 && stk[tt] >= x )tt--;
//如果栈不为空,那就说明此时的栈顶元素就是当前值左边离他最近的一个
if(tt != 0) cout<<stk[tt]<<' ';
//否则输出-1
else cout<<-1<<' ';
//把此时大于等于栈顶元素的x加入进栈中,形成单调栈
stk[++tt] = x;
}
return 0;
}