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

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

您提出的问题无法及时解决

O(n)

，因为您可以减少对其的排序，从而实现

O(n)

及时的排序。说有解决这个问题的算法

O(n)

。设元素 a 。

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

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