题目描述
给定一个长度为 N 的整数数列,输出每个数左边第一个比它小的数,如果不存在则输出 −1。
输入格式
第一行包含整数 N,表示数列长度。
第二行包含 N 个整数,表示整数数列。
输出格式
共一行,包含 N 个整数,其中第 i 个数表示第 i 个数的左边第一个比它小的数,如果不存在则输出 −1。
数据范围
1≤N≤105
1≤数列中元素≤109
样例
5
3 4 2 7 5
自己憋出了一套比较复杂的解决办法,不作为参考,纯纯练手与记录。
算法1
(暴力枚举) $O(n^2)$
时间复杂度
参考文献
C++ 代码
#include<iostream>
using namespace std;
int const N=1e5+10;
int skt[N],tt=0;
int main(){
int m;
cin>>m;
while(m--){
int s;
cin>>s;
if(tt<=0){//当栈空时,入栈后再输出-1
skt[++tt]=s;
cout<<-1<<' ';
}
else if(s>skt[tt]){//当栈非空时,且栈顶小于输入的数
cout<<skt[tt]<<' ';
skt[++tt]=s;
}
else {//当栈非空时,且栈顶大于或等于输入的数,就一直循环出栈,直到输入的数大于栈顶。
int f=0;
while(tt>0){
if(s<=skt[tt])
tt--;
else{
cout<<skt[tt]<<' ';
skt[++tt]=s;
f=1;
break;
}
}
if(!f){
skt[++tt]=s;
cout<<-1<<' ';
}
}
}
}