单调栈

单调栈

对于每一个数，找到左边（右边）和他最近的且比他最大（最小）的数

单调栈模板

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int stk[N],tt,n,x;
int main() {
    cin >> n;
    for(int i = 0;i < n; ++i) {
        cin >> x;
        while(tt && stk[tt] >= x) tt --;
        if(tt) cout << stk[tt] <<' ';
        else cout << "-1" <<' ';
        stk[++ tt] = x;
    }
    return 0;
}