$$\color{red}{算法}\color{blue}{基础课}\color{purple}{笔记and题解}\color{green}{汇总}$$

笔记：
单调栈是栈的一中特殊形式，在栈中的元素必须满足单调性（一定是单调上升或单调下降等等的规律）。
单调栈解决的常见问题：给定一个序列，求每个位置左边，离他最近且小于他的数的位置。这也就是本题了。
我们可以这样理解单调栈：
既然我们必须让元素满足单调性，那么每次插入就和栈顶作比较。
如果不满足某些性质，直接弹出栈顶，直到栈为空或满足该性质插入这个元素。

代码：

#include <bits/stdc++.h>
using namespace std ;
int st[100010], tt;
int main () {
    int n;
    cin >> n;
    while (n--) {
        int x; cin >> x ;
        while (tt && st[tt] >= x ) tt--;
        if (tt) cout << st[tt] << ' ';
        else cout << "-1 ";
        st[++ tt] = x;
    }
}