算法基础课题解合集

思路

暴力枚举 $O(n^2)$ 显然会 $T$，所以我们得想出一些能优化的性质。

我们假设当前已输入了 $5$ 和 $8$，接着输入了一个 $2$，那显然，对于 $2$ 后面输入的数据来说，答案不可能是 $5$ 和 $8$，因为总有一个 $2$ 比他们小。

所以我们可以如此维护一个单调下降的栈，每输入一个数，就判断一下有哪些数不如它，把这些数全部删掉，再看栈是否为空，如果是空的，说明没有数比它小，输出 $-1$，否则输出栈顶元素。

代码

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 100010;
int tt, stk[N];
int n, a[N];
int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i ++) {
        scanf("%d", &a[i]);
        // 单调性是显然的，因为所有比它大的数全被删掉了
        while (tt && stk[tt] >= a[i]) tt --;
        if (!tt) printf("-1 ");
        else printf("%d ", stk[tt]);
        stk[++ tt] = a[i];
    }
    return 0;
}

好啦，这篇题解到这里就结束啦！感谢观看！！！

$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\mathcal{writer\enspace by \enspace acwing}$ : $\mathfrak{天元之弈}$