给你一个长为 $N$ 的整数序列 $A_1, A_2, \dots, A_N$。定义序列 $B_1, B_2, \dots, B_N$ 如下：

对于每个 $i = 1, 2, \dots, N$，若存在整数 $j$ 满足 $1 \le j < i$ 且 $A_j < A_i$ 则 $B_i$ 等于最大的这样的 $j$，否则 $B_i$ 等于 $0$。 求 $B_1, B_2, \dots, B_N$。

好的，让我们深入剖析为什么你现有的基于数组 b 的优化能达到 $O(n)$ 的时间复杂度。

问题背景

在“Nearest Smaller Value”问题中，要求找到数组中每个元素左侧最近的一个比它小的值。你最初的解法是通过逐步查找前面的元素，找到第一个比当前值小的值，并使用一个辅助数组 b 来保存已经找到的最近较小值的位置，这样可以避免对同一个路径重复查找。

例如，假设有这样一个数组：

a = [3, 2, 5, 1, 4]

你希望找到每个元素左边最近的比它小的值，存储在 b 数组中。初始情况下， b[i] 保存的是元素 a[i] 左侧比它小的值的索引。

如何避免重复路径查找

最初的解法是通过一个简单的 while 循环逐一比较，但这样在最坏的情况下，可能会导致每次比较都遍历到数组的最左端，时间复杂度为 $O(n^2)$。然而，你通过一个跳跃数组 b 来优化这个过程：

1. 初始条件：在一开始的时候，b[i] 设置为 0，表示当前还没有找到左边比当前元素小的值。随着遍历的进行，b[i] 会被更新为找到的最近较小值的索引。

2. 查找过程的优化：假设我们在遍历元素时，遇到了一次比较失败的情况（即 a[j] 不小于 a[i]），那么我们通过 b[j] 跳跃到一个更小的索引位置，而不是逐个遍历查找。

   • 例如，如果 a[5] 的值大于 a[3]，而我们已经知道 b[5] = 1，那么我们可以直接跳到 a[1] 进行下一次比较，而不用再逐一比较 a[4], a[3] 等。
   • 这个跳跃过程依赖于 b 数组的记忆化功能，使得每次比较时，能够跳过无效的部分，快速找到可能的较小值。

为什么时间复杂度是 $O(n)$？

为了理解为什么这个过程整体的时间复杂度仍然是线性的 $O(n)$，我们可以从以下几个角度来分析：

1. 每个元素的访问次数有限：在你的算法中，每个元素只会被访问两次：一次是它作为当前要处理的元素，另一次是当它作为查找过程中被跳跃到的位置。

   具体来说，虽然存在 while 循环，但因为每次我们都会通过 b[j] 进行跳跃，跳过无效的部分，因此每次比较时，都会大幅减少需要查找的范围。每个元素只会经历一次跳跃，意味着 while 循环的总执行次数不会超过 $n$ 次。

2. 跳跃式查找减少重复计算：每个位置 i，在初始时我们可能会进行多次比较，但通过 b 数组的跳跃优化，我们能够减少不必要的比较操作。例如，如果已经知道某个元素的左侧最近较小值的位置，可以直接跳到该位置，而不用再逐个遍历。

   这样一来，尽管使用了 while 循环，每次循环中的比较次数都会随着跳跃而减少。即使数组的元素数量增加，算法的时间复杂度依然保持在线性范围内。

代码示例解读

我们通过一个简单的代码示例来进一步解释这种跳跃式查找是如何工作的：

for (int i = 1; i <= n; i++) {
    int j = i - 1;
    while (j > 0 && a[j] >= a[i]) {
        j = b[j];  // 通过跳跃到上一个更小的值的索引位置
    }
    b[i] = j;
}

在这个代码段中：

• 每次当 a[j] 不满足条件时，我们通过 b[j] 跳跃到之前的某个位置。这意味着不用再一一比较那些已经被证明无法满足条件的元素。

• 通过这样的跳跃过程，原本的 $O(n^2)$ 比较次数被压缩成了 $O(n)$。

复杂度分析

时间复杂度：$O(n)$

• 每个元素最多只会被访问两次，一次是主动处理时，另一次是通过 b 跳跃时。所以总的访问次数是 $2n$