arrays - 在未排序的数组中，将每个元素替换为右侧第一个较大的元素

Question

在未排序的数组中，我们必须用右边第一个大于当前元素的元素替换每个元素。如果右边的元素都不是更大的，则应将其替换为 -1。

例子:

3  1  2  5  9  4  8   should be converted to
5  2  5  9 -1  8 -1

我可以想到一个简单的解决方案，我们检查整个数组中的每个元素，这是一个 O(n²) 解决方案。有更好的方法吗？

Answer 1

主要思想是以相反的顺序(从右到左)处理数组。我们做了一些观察:

• 如果我们当前正在处理索引 i、k > j > i 和 A[k] ≤ A[j]，那么我们调用元素 k 无关紧要，因为它永远不会是任何元素 1, 2, ..., k
的结果
• 索引 i 的相关元素因此形成 A[i+1..n-1] 的单调严格递增子序列。

在您的示例中，相关元素的顺序将从右到左:

       []    
      [8]
    [4,8]
      [9]
    [5,9]
  [2,5,9]
  [1,5,9]

它看起来像一个栈，我们确实可以使用栈来维护迭代之间的这个序列。

当处理一个新元素时，我们首先需要找到数组元素的结果。观察结果是堆栈中最顶层的元素未被新元素无效。因此，我们可以从堆栈中弹出所有变得无关紧要的元素。那么最上面的就是我们的结果。然后我们可以推送新元素，因为它与我们的定义相关。

stack = []
A = [3, 1, 2, 5, 9, 4, 8]
result = [-1]*len(A)
for i := len(A) - 1 to 0:
    # remove all elements made irrelevant by A[i]
    while not stack.empty() && stack.top() <= A[i]:
        stack.pop()
    # now the top of the stack is the result for index i
    if not stack.empty():
        R[i] = stack.top()
    # push the new element on the stack. The stack will still contain all relevant 
    # elements in increasing order from top to bottom
    stack.push(A[i])

迭代 i 的循环不变量是“stack 包含索引 i 右侧相关元素的子序列””。易于验证，说明该算法的正确性。

每个元素最多被压入和弹出一次，所以我们的总运行时间为 O(n)。