题目描述
给定一个长度为N的整数数列,输出每个数左边第一个比它小的数,如果不存在则输出-1。
格式
共一行,包含N个整数,其中第i个数表示第i个数的左边第一个比它小的数,如果不存在则输出-1。
样例
5
3 4 2 7 5
-1 3 -1 2 2
算法1
妙极的一个思路,缩减了运算成本。
手动模拟一下样例就知道了,第一次stk里面只有3,第二次就有3,4,而第三次,直接神操作tt减到0,整个stk数组变为2,4,下一次从下标为1开始,所以依旧是输出2,不会对stk有任何改变。
整个算法完备的考虑到了数字冗余的情况,就是有一些数完全没有存在的必要,比如2比4小且4在2左边,那么对于7来说,2往左的所有数它都不会考虑。
C++ 代码
#include<iostream>
using namespace std;
const int N=1e5+10;
int n;
int stk[N],tt;
int main()
{
cin>>n;
for(int i=0;i<n;i++)
{
int x;
cin>>x;
while(tt&&stk[tt]>=x)tt--;
if(tt)cout<<stk[tt]<<' ';
else cout<<-1<<' ';
stk[++tt]=x;
}
return 0;
}