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

Question

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

[4, 2, 1, 3, 5]

我想要所有可能的对(I，j(的输出，这意味着比array[I]大的下一个最早的数字在array[j]。***特殊情况：如果您注意到样本输入[5，3，1，2，4]的相反方向，则没有大于5的元素。因此，没有配对。

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

一个O(n^2(的解决方案只是从索引i开始，然后循环到结束，当到达一个大于array[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]))