#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1e5+10;
int stk[N],tt;
int main(){
int n,x,i;
cin >> n;
for(i=0;i<n;i++){
scanf("%d",&x);
while(tt && stk[tt] >= x) tt--; //出栈
if(tt) cout << stk[tt] <<' '; //输出栈顶元素即栈中第一个小于x的值
else cout << -1 <<' ';
stk[++tt] = x; //最小元素入栈
}
return 0;
}
算法1
(暴力枚举) $O(n^2)$
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1e5+10;
int a[N],minarr[N];
int main(){
int n,i,j,minv;
bool flag = false;
scanf("%d",&n);
for(i=0;i<n;i++){
scanf("%d",&a[i]);
}
for(i=0;i<n;i++){
for(j=i;j>=0;j--){
if(a[j]<a[i]){
minarr[i] = a[j];
flag = true;
break;
}
}
if(!flag) minarr[i] = -1; flag =false;
}
for(i=0;i<n;i++){
cout << minarr[i] << ' ';
}
return 0;
}
算法2
(单调栈优化) $O(n)$
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1e5+10;
int stk[N],tt;
int main(){
int n,x,i;
cin >> n;
for(i=0;i<n;i++){
scanf("%d",&x);
while(tt && stk[tt] >= x) tt--; //出栈
if(tt) cout << stk[tt] <<' '; //输出栈顶元素即栈中第一个小于x的值
else cout << -1 <<' ';
stk[++tt] = x; //最小元素入栈
}
return 0;
}