【刷题】数据结构——单调栈【模板】

不妨设 a [ i ] a[i] a[i]左边的第一个比它小的数是 a [ j ] a[j] a[j]，设 a [ j ] a[j] a[j]左边比 a [ j ] a[j] a[j]大的数为 a [ k ] a[k] a[k]，那么 a [ k ] a[k] a[k]永远不可能是答案。 假设 a [ i + 1 ] ≥ a [ i ] a[i+1]geq a[i] a[i+1]≥a[i]，因为 a [ j ] < a [ i ] ≤ a [ i + 1 ] a[j]<a[i]leq a[i+1] a[j]<a[i]≤a[i+1]，所以最多往左找到 a [ j ] a[j] a[j]即可停下，不会继续找到 a [ k ] a[k] a[k] 假设 a [ i + 1 ] < a [ i ] a[i+1]<a[i] a[i+1]<a[i]，因为 a [ i + 1 ] < a [ j ] < a [ k ] a[i+1]<a[j]<a[k] a[i+1]<a[j]<a[k]，所以 a [ k ] a[k] a[k]不会是答案。

综上，这个栈只要保存 a [ i ] a[i] a[i]和 a [ i ] a[i] a[i]左边比 a [ i ] a[i] a[i]小的数即可，因此它单调上升的。

具体操作如下：在遍历数列时，对于每个 a [ i ] a[i] a[i]，都从栈顶往下找，找到第一个比 a [ i ] a[i] a[i]小的数， a [ i ] a[i] a[i]就在这个数上面并充当新的栈顶。

#include <iostream>
using namespace std;

const int N = 100005;

int n, stk[N], top;

int main() {
          
   
    scanf("%d", &n);
    int a;
    for (int i = 0; i < n; i ++ ) {
          
   
        scanf("%d", &a);
        while(top && stk[top] >= a) top -- ;
        if (top) printf("%d ", stk[top]);
        else printf("%d ", -1);
        stk[ ++ top] = a;
    }
    return 0;
}