arrays - O(nlog(n)) 中最小的下一个更大的元素

Question

到目前为止，为此花费了几个小时，但仍在苦苦挣扎。我可以在 O(n^2) 内轻松完成此操作，但挑战是在 O(nlog(n)) 时间内完成。

1. 未排序的数组

2. 需要找到最小 A[j] 的索引，使得 A[j] > A[i] 和 j > i 未排序数组中的每个元素

所以本质上是大于元素的最小元素，并且在数组中位于它的右侧。

如果找不到元素，则索引为-1。

结果是我们正在寻找的对应索引值的数组。

示例:

Input: [80; 19; 49; 45; 65; 71; 76; 28; 68; 66]
Output: [-1; 7; 4; 4; 9; 6; -1; 9; -1; -1]

目前的尝试是扫描输入数组并为每个元素创建一个值-索引对，将它们插入一个新数组并根据值对其进行排序。然后可能是二进制搜索或自平衡 BST 的一些变体，但实际的解决方案并没有出现在脑海中。

这是 Next Greater Element 问题的轻微变体。

如有任何帮助，我们将不胜感激。

Answer 1

我觉得这道题和寻找节点的后继者很像。如果您可以想象数组中的所有值都在 BalancedBST 中，例如 AVL 树。 这里唯一的技巧是我们需要从数组中数字右边的值中找到后继者。所以这里的技巧实际上是从右到左查询。

所以我们从数组的最后一个元素开始，将其放入 BST 中，然后查询该元素的后继元素。对数组中从右到左的每个元素继续执行此操作。

这将导致 O(NlgN)，因为插入以及在 BST 中找到后继者在最坏的情况下是 logN。