数组中最远的较小元素

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

Ex:
输入：6 3 1 8 2 9 7
输出：2 2 -1 7 -1 7 -1

解释：

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

一个想法是：

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

Java代码：

    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的解决方案相比，上述算法在以下最坏情况下会更好：

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

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)。