题解

这是一个单调栈的应用。可以参考 OI-Wiki 或者这里：链接描述
题目很版，也不想某谷卡常。用 STL 就行。这里不多讲。

#include <bits/stdc++.h>
using namespace std;
stack<int> a;
int sz[30000005],ans[30000005]; 
int main(){
    int n;
    cin >>n;
    for(int i=1;i<=n;i++)cin >> sz[i];
    for(int i=n;i>=1;i--){
        while(a.size() and sz[a.top()]<=sz[i])a.pop();
        ans[i]=!a.size()?0:a.top();
        a.push(i);
    }for(int i=1;i<=n;i++)cout << ans[i] << " ";
    return 0;
}

手写单调栈：

#include <bits/stdc++.h>
using namespace std;
stack<int> a;
int sz[30000005],ans[30000005],sta[30000005]; 
int main(){
    int n,idx=1;
    cin >>n;
    for(int i=1;i<=n;i++)cin >> sz[i];
    for(int i=n;i>=1;i--){
        while(idx and sz[sta[idx]]<=sz[i])idx--;
        ans[i]=!idx?0:sta[idx];
        sta[++idx]=i;
    }for(int i=1;i<=n;i++)cout << ans[i] << " ";
    return 0;
}