题目描述

给定一个长度为N的整数数列，输出每个数左边第一个比它小的数，如果不存在则输出-1。

样例

5
3 4 2 7 5

-1 3 -1 2 2

算法

(单调栈)

1. 输出printf()结果不一定要放在最后
2. 每一次for()循环都会执行的代码往往放在后面，比如这里的s[++ tt] = x，带有条件判断的放在前面。
3. 之前疑惑-1怎么输出，当单调栈s没有元素的时候tt = 0就表示没有符合条件的元素
4. 题目要求 左边比自己小的第一个元素。所以构造的单调栈s中维护的是一个 单调递增的序列，所以碰到s[tt] >= x的情况，也就是当前要加入的元素x比栈顶元素s[tt]小，就将栈顶元素s[tt]去掉，因为x是一定要加进来的，但是单调栈s我们是可以修改的。
5. 最后判断，当跳出while()循环的时候，要不然是tt = 0了，我们就输出-1，要不然就是s[tt] < x，这时候我们输出s[tt]，因为此时栈顶元素就是满足 左边第一个比x小的元素，然后把x放入单调栈s中。不能先放x再输出，因为此时的栈顶元素就是x了，不再是x之前的s[tt]了。这点要注意一下。

时间复杂度

$O(n)$

C++ 代码

#include <iostream>

using namespace std;

const int N = 100010;

int tt;
int s[N];

int main()
{
    int n;
    cin >> n;

    while(n --)
    {
        int x;
        cin >> x;

        while(tt && s[tt] >= x) tt --;

        if(!tt) printf("-1 ");
        else printf("%d ", s[tt]);

        s[++ tt] = x;
    }
}

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla