单调栈

找到每个数左边离他最近且比他小的数。

cpp

3 4 2 7 5
-1 3 -1 2 2

考虑方式和双指针类似。

先考虑 找到每个数左边离他最近且比他小的数 这个问题的暴力做法：二重循环

cpp

for (int i = 0, j; i < n; i ++) {
    for (j = i - 1; j >= 0; j --) {
        if (a[j] < a[i]) {
            cout << a[j] << ' ';
            break;
        }
    }
    if (j == -1) {
        cout << -1 << ' ';
    }
}

首先要研究的就是 i, j 的位置关系。比如是否可以让 j 不从 i - 1 开始移动，而是观察当 i 向右移动一位之后，j 对应的移动方式。

注意到：针对 a[i + 1] 和 a[i] 的大小关系可分为两种情况：

$a_{i + 1} > a_{i}$ ，则 a[i + 1] 左边离它最近且比它小的数就是 a[i]
$a_{i + 1} \leq a_{i}$ ，由于 $a_{j + 1} \sim a_{i - 1} \geq a_{i}$ ，那么 j 只能不动或者左移
也就是说，j 的取值是呈现 要么跳跃，要么一个一个左移 的情形

cpp

cout << -1 << " ";
for (int i = 1, j = 0; i < n; i ++) {
    if (a[i] > a[i - 1]) {
        j = i - 1;
        cout << a[i - 1] << " ";
        continue;
    }

    for (j; j >= 0; j --) {
        if (a[j] < a[i]) {
            cout << a[j] << " ";
            break;
        }
    }

    if (j == -1) {
        cout << -1 << ' ';
    }
}

上述代码已经可以 AC 了，我们继续思考：j 的跳跃会出现这种情况吗？

如果不会，那么显然由于 i, j 的遍历都是最多遍历每个点一次，那么时间复杂度最多是 $O (2 n)$ 的。

于是我们继续思考当 $a_{i + 1} \leq a_{i}$ 的时候会发生什么，显然我们只能用 $a_{j}$ 来和 $a_{i + 1}$ 作比较了：

$a_{j} < a_{i + 1}$ ：这说明 j 保持不变即可
$a_{j} \geq a_{i + 1}$ ：这是最不愿意发生的事，说明 j 要左移了
- 由于 $a_{j}$ 是最靠近 $a_{i}$ 且比它小的数，因此在 $a_{j}$ 的左边可能会有比它更小的数
- 1 3 4 5 2 就是例子，当 j 跳跃到 a[2] = 4 时，下一步要回退两格到 1

这么说，时间复杂度没法下降了？幸运的是，我们还是有点发现的：那就是我们寻找的是 $a_{j}$ 的左边可能会有比它更小的数，也就是说，我们并不关心 $a_{j}$ 左边比它大的数，这些数通通可以剪枝掉。

欸？这个问题为什么这么似曾相识？我们变换一下说法：当 $a_{j} \geq a_{i + 1}$ 时，我们需要依次找到 $a_{j}$ 左边最靠近 $a_{j}$ 且比它小的数 $a_{u}$ ，并将其和 $a_{i + 1}$ 作比较。如果依然有 $a_{u} \geq a_{i + 1}$ ，那么继续找 $a_{u}$ 左边最靠近 $a_{u}$ 且比它小的数 $a_{t}$ ……

因此可以考虑用栈来存储这样的数据。

对于任意数据 $a_{i}$ ，此时栈顶存放它左边且最靠近 $a_{i}$ 且比它小的数 $a_{j}$
- 首先将 $a_{i}$ 入栈
- 栈内满足：每次弹出元素 $a_{i}$ 的左边且最靠近且比它小的元素 $a_{j}$ 来到栈顶
- 这是因为压栈的时候就是按照这个方式压入栈的
- 栈内保持单调递减
对于下个数据 $a_{i + 1}$ ，维护方法为：
- 如果 $a_{i} < a_{i + 1}$ ，说明栈顶 $a_{i}$ 是满足要求的数，无操作
- 如果 $a_{i} \geq a_{i + 1}$ ，说明栈顶 $a_{i}$ 不满足要求，弹出
- 由于栈的性质，新栈顶 $a_{j}$ 就是刚才最靠近 $a_{i}$ 且比它小的数，与 $a_{i + 1}$ 进行比较
- 重复上述操作，直到找到要求的数或者栈空
- 操作完成后，记得要将 $a_{i + 1}$ 入栈

每次操作完成后都将当前数入栈这一操作：保证了下次遇到 $a_{i} < a_{i + 1}$ 时可以直接取出。

核心代码：

cpp

// ...
    for (int i = 0; i < n; i ++) {
        int x;
        cin >> x;

        while (tt && stk[tt] >= x) {
            tt --;
        }

        if (tt) {
            cout << stk[tt] << " ";
        }
        else {
            cout << -1 << " ";
        }

        stk[++ tt] = x;
    }

以上这种思考逻辑完全是正向的：

首先思考 i, j 之间的关系：j 一定是跳跃 + 左移两种情况的
然后发现 j 在左移的过程中，是不需要考虑左边比它大的数的
然后发现结构的不变性：找到的是 $a_{j}$ 左边最靠近且比它小的数 $a_{u}$ ，循环操作
最后考虑用栈存储它们：
- 压入栈的方式为：每次保证栈顶都是最靠近 $a_{i}$ 且比他小的数后压入 $a_{i}$
- 弹出栈的情况为：每次弹出后都保证栈顶是最靠近且比它小的数

另一种思考方式

对于序列 $a_{n}$ 中这样一类元素对： $a_{i} > a_{j}$ 同时 $i < j$ 。也就是所谓的 逆序对。由于 $a_{j}$ 在 $a_{i}$ 的左边且比它小，这种情况下可以断言：对于 $a_{j}$ 及其右边的数， $a_{i}$ 永远不会作为答案输出：

如果比 $a_{j}$ 大，那么向左搜索到 $a_{j}$ 就停止了，不会取到 $a_{i}$
如果比 $a_{j}$ 小，那么会直接跳过 $a_{j}, a_{i}$

因此在我们考察 $a_{j}$ 后面的元素时，应当删除该元素之前所有逆序对中较大的元素。这样就构成了一个 严格单调递增序列。

假设我们现在已经有了一个这样的序列，我们来探究如何维护它：

序列最右边的元素为 $a_{j}$ ，待考察的元素为 $a_{i}$ ，我们要找到它对应的答案
首先该序列已经去掉了所有永远不会成为答案的数，剩下的数分两种情况讨论：
- $a_{j} < a_{i}$ ：无问题，直接将 $a_{i}$ 插入依然是严格单调递增序列，答案是 $a_{j}$
- $a_{j} \geq a_{i}$ ：此时在备选答案序列中从右往左查询，找到的第一个比 $a_{i}$ 小的数就是最靠近 $a_{i}$ 且比它小的数 $a_{u}$ 了
- 而对于 $a_{u} \sim a_{j}$ 中的所有数，它们对于 $a_{i + 1}$ 以及后面的数（由于和 $a_{i}$ 构成了逆序对）因此不会成为答案

对于这种只考虑 从右往左 查询（某一个方向）的数据结构，我们可以用栈来存储，也就是从顶往下查询。

对于待考察元素 a[i]
考虑栈顶元素 stk[tt] 和它的大小关系
- stk[tt] < a[i]，则答案为 stk[tt]，直接加入 a[i]，依然是单调栈
- stk[tt] >= a[i]，则不断弹出栈顶元素 tt --，直到栈顶元素符合要求
- 这一步也就是单调栈维护（清除逆序对）的做法

似乎这种思考方式更清爽简洁（逆序对中较大的数不会成为后面的答案），但是较难想到。

用 STL 的 stack 再写一次：

单调栈 ​

另一种思考方式 ​

单调栈

另一种思考方式