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

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