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

主要思想是以相反的顺序（从右到左）处理数组。我们进行一些观察：

• 如果我们当前正在处理索引 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

每个元素最多被推送和弹出一次，因此我们的总运行时间为 Ο（n） 。