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

#include <bits/stdc++.h>
using namespace std;//用数组实现栈
int n, a[1000005], l[1000005], r[1000005], st[1000005]/*手写栈*/, s,cur;//O(N)
int main() {
    cin >> n;
    for (int i = 0; i < n; i++) {
        scanf("%d", &a[i]);
    }
    for (int i = 0; i < n; i++) {//遍历阶段
        while (s > 0 && a[i] <= a[st[s - 1]]) {
            cur= st[--s];//cur是当前弹出的索引
            r[cur] = i;
            l[cur] = s == 0 ? -1 : st[s - 1];
        }
        st[s++] = i;
    }
    while (s > 0) { //清算阶段
        cur = st[--s];
        r[cur] = -1;
        l[cur] = s == 0 ? -1 : st[s - 1];
    }
    for (int i = n - 2; i >= 0; i--) { //修正阶段
        if (r[i] != -1 && a[i] == a[r[i]]) {
            r[i] = r[r[i]];
        }
    }
    for (int i = 0; i < n; i++) {
        printf("%d %d\n", l[i], r[i]);
    }
}

【算法讲解052【必备】单调栈-上】 https://www.bilibili.com/video/BV1HH4y1X7T9/?share_source=copy_web&vd_source=5065fa61022691e8df35c771a30e6d29