题解 | 单调栈结构(进阶)

#include <iostream>
using namespace std;
const int N = 1e6;
int arr[N];
int stk[N];
int ans[N][2];
int n,r;
void compute(){
    r = 0;
    int cur;
    for (int i = 0; i < n; i++)
    {
        while( r > 0 && arr[stk[r-1]] >= arr[i])
        {
            cur = stk[--r];
            ans[cur][0] = r>0 ? stk[r-1]:-1;
            ans[cur][1] = i;
        }  
        stk[r++]=i;
    }
    while(r > 0)
    {
        cur = stk[--r];
        ans[cur][0] = r>0 ? stk[r-1]:-1;
        ans[cur][1] = -1;
    }

    for (int i = n-2; i >= 0;i--){
        if (ans[i][1] != -1 && arr[ans[i][1]] == arr[i])
        ans[i][1] = ans[ans[i][1]][1];
    }
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin>>n;
    for (int i = 0; i < n; i++)
    cin>>arr[i];
    compute();
    for (int i = 0; i < n; i++)
    cout<<ans[i][0]<<' '<<ans[i][1]<<endl;
    return 0;
}