数组中每个元素右侧的最大元素 [英] Greatest element present on the right side of every element in an array

问题描述

我已经得到一个数组（由n个元素组成），并且我必须在每个元素的右侧找到比其自身（当前元素）更大的最小元素。

I have been given an array (of n elements) and i have to find the smallest element on the right side of each element which is greater than itself(current element).

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

是否可能在 O（n）中解决此问题。我想到要从右侧遍历数组（从n-2开始），然后为其余元素构建一个平衡二进制搜索树，因为要在其中搜索立即大于当前元素的元素元素将是O（logn）。

Is it possible to solve this in O(n).? I thought of traversing the array from the right side (starting from n-2) and building a balance binary search tree for the remaining elements, as searching in it for an element which is immediately greater than the current element would be O(logn) .

因此时间复杂度为O（n *（log（n））。

Hence time complexity would come out to be O(n*(log(n)).

是

推荐答案

您提出的问题无法在 O（ n）时间，因为您可以减少对它的排序，从而实现在 O（n）时间中进行排序。
说存在一个可以解决 O（n）中的问题的算法。
让元素 a 出现。

The problem you present is impossible to solve in O(n) time, since you can reduce sorting to it and thereby achieve sorting in O(n) time. Say there exists an algorithm which solves the problem in O(n). Let there be an element a.

该算法还可用于查找最小元素，该元素位于 a的左且比 a大 （通过在运行算法之前反转数组）。
还可以用于在 right （或向左），并且比 a 小（通过在运行算法之前取反元素）。

The algorithm can also be used to find the smallest element to the left of and larger than a (by reversing the array before running the algorithm). It can also be used to find the largest element to the right (or left) of and smaller than a (by negating the elements before running the algorithm).

因此，在运行算法fou之后r次（以线性时间为单位），您知道哪个元素应该在每个元素的右侧 。为了以线性时间构造排序后的数组，您需要保留元素的索引而不是值。您首先要按照线性时间跟随大于指针找到最小的元素，然后在另一个方向进行另一遍操作以实际构建数组。

So, after running the algorithm four times (in linear time), you know which elements should be to the right and to the left of each element. In order to construct the sorted array in linear time, you'd need to keep the indices of the elements instead of the values. You first find the smallest element by following your "larger-than pointers" in linear time, and then make another pass in the other direction to actually build the array.

这篇关于数组中每个元素右侧的最大元素的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！