arrays - 最大元素出现在数组中每个元素的右侧

Question

我得到了一个数组(包含 n 个元素)，我必须找到每个元素右侧大于其自身(当前元素)的最小元素。

For example :
   Array =     {8,20,9,6,15,31}
Output Array = {9,31,15,15,31,-1} 

是否有可能在 O(n) 中解决这个问题？我想从右边开始遍历数组(从 n-2 开始)并为剩余的元素构建平衡二叉搜索树，因为在其中搜索一个立即大于当前的元素元素将是 O(logn) 。

因此时间复杂度为 O(n*(log(n))。

有没有更好的方法来解决这个问题？

Answer 1

您提出的问题不可能在O(n) 时间内解决，因为您可以减少对它的排序，从而在O(n) 时间内实现排序。假设存在一种算法可以解决 O(n) 中的问题。假设有一个元素a。

该算法还可用于找到左侧且大于a 的最小元素(通过在运行算法之前反转数组)。它还可用于查找右侧(或左侧)和小于a 的最大元素(通过在运行算法之前取反元素)。

因此，在运行该算法四次(以线性时间)后，您知道哪些元素应该在每个元素的右边和左边。为了在线性时间内构造排序数组，您需要保留元素的索引而不是值。您首先通过在线性时间内跟随“大于指针”找到最小的元素，然后在另一个方向上进行另一次传递以实际构建数组。