给定未排序的数组，对于每个元素，找到比它大的最早的下一个元素的索引

Question

我有一个具有不同数字的未排序数组。

[4, 2, 1, 3, 5]

我想要所有可能对 (i, j) 的输出，这意味着下一个大于数组 [i] 的最早数字在数组 [j] 中。 *** 特殊情况：如果你注意到样本输入的反转，[5, 3, 1, 2, 4]，没有大于 5 的元素。因此，没有对。

对于原始输入，答案将是 [[0, 4], [1, 3], [2, 3], [3, 4]]

O(n^2) 的解决方案将从索引 i 开始，然后循环到结尾并在到达大于数组 [i] 的元素时停止。有没有办法将其降低到 O(n log n) 或 O(n)？

Answer 1

您可以使用堆栈在 O(n) 内得到结果。要么前进，要么后退。但今后将不会对输出进行排序。 Unshift 将一个元素放在前面。这个想法是我们总是可以使用堆栈的顶部并丢弃不再重要的东西，所以我们只将堆栈上的所有东西压入和弹出一次。

function pairs(arr) {
    let stack = [], solution = []
    for (let i = arr.length - 1; i >= 0; i--) {
        while (stack.length > 0 && stack[stack.length - 1][0] < arr[i])
            stack.pop() //         ^^^^^^^^^^peek^^^^^^^^^
        if (stack.length > 0)
            solution.unshift([i, stack[stack.length - 1][1]])
        stack.push([arr[i], i])
    }
    return solution
}
console.log(pairs([4, 2, 1, 3, 5]))

给定未排序的数组，对于每个元素，找到比它大的最早的下一个元素的索引

Given unsorted array, for each element, find index of the earliest next element that is larger than it

algorithm

math

optimization