单调栈

原理

应用

求每个数的左（或右）边第一个比它小（或大）的数。

模板题

AcWing-830-单调栈

#include <iostream>
#include <stack>
using namespace std;

const int N = 100010;
int n, a[N];
stack<int> s;

int main () {
    scanf("%d", &n);
    for (int i = 1; i <= n; ++ i) scanf("%d", &a[i]);

    for (int i = 1; i <= n; ++ i) {
        int cur = a[i];
        while (!s.empty() && s.top() > cur) s.pop();

        printf("%d ", s.empty() ? -1 : s.top());

        s.push(cur);
    }
    return 0;
}