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

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).让我们有一个元素一个.

该算法也可以用来寻找最小的元素左侧的和较大的比一(通过反转阵列运行算法之前).它也可以用来寻找最大的元素右(或左)和更小的比一个(由否定要素运行算法之前).

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