数组中最远的小元素

Question

在未排序的正整数数组中，如何以最有效的方式找出每个元素右侧最远的较小元素？

例如：
输入：6 3 1 8 2 9 7
输出：2 2 -1 7 -1 7 -1

解释：

对于 6，它右侧的较小元素是 [3, 1, 2]。因为最后一个最小的元素是 2，所以它离 6 最远。对于其他人来说也是如此。如果不存在这样的数字，则答案为“-1”

Answer 1

一种想法是：

• 让我们称原始数组 A
• 保留一个大小为 n 的数组 min[]，其中 min[i] 表示子数组 A[i..n-1] 的最小值。显然，min[i] <= min[i+1]。
• 现在在 A 上从右向左移动。在每个索引 i 上，对 min[i+1..n-1] 进行二分搜索以找到最远的较小值。

爪哇代码：

    int[] A = { 6, 2, 3, 10, 1, 8 };
    int n = A.length;
    // calculate min
    int[] min = new int[n];
    min[n - 1] = A[n - 1];
    for (int i = n - 2; i >= 0; i--)
        min[i] = Math.min(A[i], min[i + 1]);
    // calculate results
    int[] results = new int[n];
    results[n - 1] = -1;
    for (int i = n - 2; i >= 0; i--) {
        int left = i; // after the binary search, A[left] would be the answer
        int right = n - 1;
        while (left < right) {
            int mid = left + (right - left + 1) / 2;
            if (min[mid] < A[i])
                left = mid;
            else
                right = mid - 1;
            if (min[left] < A[i])
                results[i] = min[left];
            else
                results[i] = -1;
        }
    }

空间复杂度 O(n)

所有情况的时间复杂度为 O(nlogn)。

与@vivek_23 的解决方案相比，上述算法在以下最坏情况下会更好：

想象一下有 n 个元素的 A 的情况如下

A = [ n/2 n/2 .. n/2 1 2 .. n/2]

如果我们使用@vivek_23 建议的堆栈解决方案，

• 在查找任何前 n/2 个元素（均值为 n/2）中最远的较小元素的步骤中，st1 现在应为 [1 2 .. n/2]
• 对于每个值为 n/2 的元素，除了 n/2 之外的所有 st1 元素都将被转移到 st2 以找到最远的较小元素 n/2 - 1。之后 st2 中的所有元素将被转移回 st1。这导致 O(n) 的最坏情况性能。由于有 n/2 个元素，总的最坏时间性能是 O(n^2)。