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

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))。

是否有更好的解决方案呢？

- poorvank

Answer 1

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

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

因此，在线性时间内运行该算法四次后，您将知道每个元素左侧和右侧应该是哪些元素。 为了以线性时间构建排序的数组，您需要保留元素的索引而不是值。 您首先通过在线性时间内遵循“大于指针”来查找最小元素，然后向另一个方向再进行一遍通确切地构建数组。

- YaronK

---

这并不等同于排序，快速排序中每一步都是查找任何元素a的位置，这在O(n)中完成。或者我是否误解了您从排序中的简化？ - amit

看起来对我来说很不错，至少用于对不同数字进行排序（我非常确定这已经足够了？我不知道）。@amit：在对v和reverse(v)上运行算法后，对于每个元素，您都知道应该出现在其右侧的元素的索引（它可能是其右侧的下一个最小元素或其左侧的下一个最小元素）。因此，从任何起始元素i开始，您可以在每个元素中以O（1）时间构建具有索引> = i的解决方案的一部分。翻转符号并重复将为您提供部分左侧（即具有索引<= i的部分）。 - j_random_hacker

明白了，我以为你要获取一个元素的单个位置，这在O(n)内是可以完成的。谢谢澄清。 - amit

Answer 2

其他人已经证明，一般情况下无法在O(n)的时间内解决问题。

然而，在最大元素的大小为m时可以在O(m)的时间内解决问题。

这意味着在某些情况下（例如，如果您的输入数组已知是整数1到n的排列），则可以在O(n)的时间内解决问题。

下面的代码显示了该方法的实现，该方法建立在计算下一个更大元素的标准方法上。（有一个很好的解释这种方法的geeks for geeks ）

def next_greater_element(A):
    """Return an array of indices to the next strictly greater element, -1 if none exists"""
    i=0
    NGE=[-1]*len(A)
    stack=[]
    while i<len(A)-1:
        stack.append(i)
        while stack and A[stack[-1]]<A[i+1]:
            x=stack.pop()
            NGE[x]=i+1
        i+=1
    return NGE

def smallest_greater_element(A):
    """Return an array of smallest element on right side of each element"""
    top = max(A) + 1
    M = [-1] * top # M will contain the index of each element sorted by rank
    for i,a in enumerate(A):
        M[a] = i
    N = next_greater_element(M) # N contains an index to the next element with higher value (-1 if none)
    return [N[a] for a in A]


A=[8,20,9,6,15,31]
print smallest_greater_element(A)

这个想法是找到下一个索引更大的按大小排序的元素。因此，这个下一个元素将是出现在右边的最小的元素。

- Peter de Rivaz

Answer 3

这不能在O（n）中完成，因为我们可以将元素唯一性问题（已知基于比较的解决方法为Omega（nlogn））归约到它。

首先，让我们对问题进行一点扩展，这不会影响其难度：

给定一个数组（n个元素），我必须找到每个元素右侧大于/等于自身（当前元素）的最小元素。

添加的是我们允许元素等于它本身（和右侧），而不仅仅是严格大于。

现在，给定元素唯一性实例arr，运行此问题的算法，并查看是否存在任何元素i使得arr[i] == res[i]，如果没有回答“所有不同”，否则回答“不全相同”。

然而，由于元素唯一性是基于比较的Omega（nlogn），这也使得该问题成为Omega（nlogn）。

---

（1） 添加相等性并不会使问题更加困难的一个可能的理由是——假设元素是整数，我们可以将 i/(n+1) 加到数组中的每个元素上，现在对于每两个元素，如果 arr[i] < arr[j]，那么 arr[i] + i/(n+1) < arr[j] + j/(n+1)，但如果 arr[i] = arr[j]，那么如果 i<j，arr[i] + i/(n+1) < arr[j] + j/(n+1)，我们可以使用相同的算法来解决相等性的问题。

- amit