python/TangDou/AcWing/832.cpp

#include <bits/stdc++.h>

using namespace std;

const int N = 100010;
int n;
int stk[N], tt;


//单调栈
void ddz() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        int x;
        scanf("%d", &x);
        //单调栈其实大多数就这一个应用,时间复杂度是O(N)，比暴力法优化了一个数量级
        //while (tt) 是指栈不是空的
        while (tt && stk[tt] >= x) tt--; //如果数组中有元素存在，并且从右向左走，还存比x大的数据，那么需要将这些比x大的数据弹出
        //if(tt)是指栈不是空的
        if (tt) printf("%d ", stk[tt]);
        else printf("-1 ");
        //再加入一个数据x
        stk[++tt] = x;
    }
}

int a[N];

//暴力做法
// 思考暴力作法的性质，我们可以用一个栈来存储i左边的所有元素，最开始栈是空的，当我们的i指针每往右边移动一下的话，我们就向栈中加入一个数
// 这样如果存在逆序对，那么前面的就一定不会输出出来。换句话说就不用入栈了，入了也没用。
// 这种思路，其实是因为要求：找到左边第一个比i小的（大的）元素j在什么地方，如果在j左边存在一个k，这个k比j大，那么就没有必要生存了。
void baoli() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%d", &a[i]);
        for (int j = i - 1; i >= 0; j--) {
            if (a[i] > a[j]) {
                printf("%d ", a[j]);
                break;
            }
        }
    }
}

//单调栈
int main() {
    //输入+输出重定向
    freopen("../AcWing/N4/832.txt", "r", stdin);
    //单调栈
    ddz();
    //暴力做法
    //baoli();
    //关闭文件
    fclose(stdin);
    return 0;
}