单调栈模板

#include <bits/stdc++.h>
using namespace std;
const int int = 1e9;
const int maxn = 1e5 + 5;
int a[maxn];
int Lmin[maxn], Rmin[maxn];//以当前位置为最小值,能扩展到哪里
int Lmax[maxn], Rmax[maxn];//以当前位置为最大值,能扩展到哪里
stack<int> s;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    a[0] = a[n + 1] = -inf;
    for (int i = 1; i <= n + 1; i++) {
        while (!s.empty() && a[s.top()] >= a[i]) {
            Rmin[s.top()] = i; s.pop();
        }
        s.push(i);
    }
    while (!s.empty()) s.pop();
    for (int i = n; i >= 0; i--) {
        while (!s.empty() && a[s.top()] >= a[i]) {
            Lmin[s.top()] = i; s.pop();
        }
        s.push(i);
    }
    a[0] = a[n + 1] = inf;
    while (!s.empty()) s.pop();
    for (int i = 1; i <= n + 1; i++) {
        while (!s.empty() && a[s.top()] <= a[i]) {
            Rmax[s.top()] = i; s.pop();
        }
        s.push(i);
    }
    while (!s.empty()) s.pop();
    for (int i = n; i >= 0; i--) {
        while (!s.empty() && a[s.top()] <= a[i]) {
            Lmax[s.top()] = i; s.pop();
        }
        s.push(i);
    }
    return 0;
}