我得到了一个数组（由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)
因此，时间复杂度将变为O（n *（log（n））。
有没有更好的方法来解决这个问题？
您提出的问题无法及时解决O(n)，因为您可以减少对其的排序，从而实现O(n)及时的排序。说有解决这个问题的算法O(n)。设元素 a 。
该算法也可以用来寻找 最小 的元素 左侧 的和 较大的 比 一 （通过 反转阵列 运行算法之前）。它也可以用来寻找 最大 的元素 正确 的（或左）和 更小的 比 一个 （由 否定要素 运行算法之前）。
因此，在算法四次运行（线性时间）后，您知道 每个 元素的右边和左边应该有哪些元素。为了在线性时间内构造排序后的数组，您需要保留元素的索引而不是值。您首先要在线性时间内跟随“大于指针”来找到最小的元素，然后在另一个方向进行另一遍以实际构建数组。
