这就是一个单调栈的模板题
首先,先了解什么是单调栈
单调栈:找到数组每个元素左侧最接近它且小于它的数的下标
简单来说:就是向左走,直到找到离他最近的小于它的数的位置
然后,看看模板怎么写
int stk[N];
int tt = 0;
for (int i = 1; i <= n; i ++) {
while (tt && a[stk[tt]] >= a[i]) tt --;
ans[i] = stk[tt];
stk[++tt] = i;
}
最后,写个头文件,套一下公式,然后输出
#include<bits/stdc++.h>
using namespace std;
const int N=3e6+10;//确定一个固定值
int a[N],stk[N],ans[N],tt;
int main() {
int n;
scanf("%d",&n);
for(int i=1; i<=n; i++)scanf("%d",&a[i]);
for(int i=n; i; i--) {
while(tt>=1&&a[stk[tt]]<=a[i])tt--;
ans[i]=stk[tt];
stk[++tt]=i;
}
for(int i=1; i<=n; i++) {//输出结果
cout<<ans[i]<<endl;
}
return 0;
}