单调栈

单调栈是指栈内的元素单调递增或者递减，主要是以$O(n)$的时间解决NGE问题（Next Greater Element）。就是在每个元素中，找到下一个比他大的1数。（或者其他的变式）。

可以类似于身高，2只能看到4是第一高的，1只能看到2是第一高的…同理。

这一过程，我们可以从后往前面扫描，给出源代码：

#include <bits/stdc++.h>
using namespace std;
const int N = 5000100;
int a[N], res[N], n;
stack<int> s;

int main() {
    cin >> n;
    for(int i = 1; i <= n; i++) cin >> a[i];
    
    for(int i = n; i >= 1; i--) {
        while(!s.empty() && a[s.top()] <= a[i]) s.pop();
        if(!s.empty()) res[i] = s.top();
        else res[i] = 0;;
        s.push(i);
    }
    for(int i = 1; i <= n; i++) cout << res[i] << " ";
}

思想就是，比如从最后的3开始。一开始3进栈，然后指向4的时候，因为4比栈顶的值大，那就说明4的右边没有比她大的数，所以3出来4进去。接下来就是2，因为2比栈顶的值4小，所以这个时候2的右边第一个大的数就是4，存储4，并且2进栈。。。以此类推，就能得到序列了。