单调栈

思路分析

栈的题型基本也就这一种

暴力做法

本题如果采用暴力对于每一个数，我们从它左边第一个数依次向左枚举，这样时间复杂度是$O(n ^ 2)$的

优化的性质

从前往后枚举每一个数字，枚举到的当前数字如果比前面数字小，那么前面那个数字对于这个数字的后面数就是没有影响的了。因为如果前面那个数字满足大小关系，那么当前数字也是满足的，由于当前数字更靠右，因此它会是一个更优解

由于上述性质，我们可以采用单调栈

我们依次从前往后处理每一个数字

对于一个数字，如果它小于等于当前栈顶元素，那栈就不断出栈（当前数字是更优解）

每次找出离该元素左边且最近的小于它的元素则是栈顶

最后将当前元素入栈

代码

#include <iostream>

using namespace std;

const int N = 100010;

int stk[N], tt;

int main()
{
    int n;
    cin >> n;
    while (n -- )
    {
        int x;
        scanf("%d", &x);
        while (tt && stk[tt] >= x) tt -- ; // 如果栈顶元素大于等于当前元素，则当前元素是最优解，栈顶出栈
        if (!tt) printf("-1 ");  //栈空时则无解
        else printf("%d ", stk[tt]);  //栈顶为答案，输出栈顶
        stk[ ++ tt] = x;  //当前元素入栈
    }

    return 0;
}