在一个未排序的阵列，我们有由第一元件，以取代每一元素以比所述当前元素较大的权利。如果没有任何元素的权利都更大，那么它应该被替换 1 。

In an unsorted array, we have to replace every element by the first element to the right that is larger than the current element. If none of the elements to the right are bigger then it should be replaced with -1.

例如：

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

我能想到的小事解决方案，我们检查每一个元素与整个数组这是一个的Ο（N²）的解决方案。有没有更好的方式来做到这一点？

I can think of the trivial solution where we check every element with the entire array which is an Ο(n²) solution. Is there a better way to do this?

推荐答案

其主要思想是处理以相反的顺序排列（从右到左）。我们提出几点意见：

The main idea is to process the array in reverse order (from right to left). We make a few observations:

如果我们目前正在处理索引的我的 K> J>时我和 A [K]≤A [J] ，则称元素的 K 的无关紧要的，因为它永远不会是这个结果对于任何元素的 1，2，...，K 的 右键指数的相关元素的因此，我的形成的单调严格递增序列A [1 + 1 ... N-1] If we are currently processing index i, k > j > i and A[k] ≤ A[j], then we call element k irrelevant, because it will never be the result for any of the elements 1, 2, ..., k The relevant elements right of an index i therefore form a monotonically strictly increasing subsequence of A[i+1..n-1].

在你的榜样，相关要素的顺序是从右到左：

In your example, the sequences of relevant elements would be from right to left:

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

它看起来像一个堆栈，我们的确可以使用堆栈来维持迭代之间的顺序。

It looks like a stack, and we can indeed use a stack to maintain this sequence between iterations.

在处理一个新的元素，我们首先需要找到结果的数组元素。该观察的结果是在栈上的最顶层元素是没有的由新元素无效。因此，我们可以刚刚从栈中弹出，已成为无关紧要的所有元素。是什么，然后在顶部是我们的结果。然后，我们可以把新的元素，因为它是有关根据我们的定义。

When processing a new element, we first need to find the result for the array element. The observation is that the result is the topmost element on the stack that is not invalidated by the new element. Therefore we can just pop from the stack all elements that have become irrelevant. What is then on the top is our result. We can then push the new element because it is relevant by our definition.

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

循环不变式迭代我是 堆栈包含相关元素的子向右首页的我 的。这是很容易验证，并暗示该算法的正确性。

The loop invariant for iteration i is "stack contains the subsequence of relevant elements to the right of index i". It is easy to verify and implies the correctness of this algorithm.

每一个元素入栈和出栈最多一次，所以我们的Ο（N）的。

Every element is pushed and popped at most once, so we have a total runtime of Ο(n).