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

Question

在一个未排序的数组中，我们需要用其右侧第一个比当前元素大的元素替换每个元素。如果右侧没有比该元素大的元素，则应将其替换为-1。

示例:

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

我可以想到一个平凡的解决方案，即检查每个元素与整个数组，这是一个Ο(n²)的解决方案。有更好的方法吗？

- Ritesh Mahato

---

应该是 -1 2 5 9 -1 8 -1 吗？ - lakshmen

@lakesh：据我所知，5是第一个大于3且位于第一个位置右侧的值。 - Niklas B.

@NiklasB。哦，好的。我理解错了问题。 - lakshmen

@nwellnhof：真的吗？为什么？对我来说并不是显而易见的。 - Niklas B.

@nwellnhof: 你是怎么得出平均情况下O(n)时间复杂度的？能再解释一下吗？ - Ritesh Mahato

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右侧相关元素的子序列"。 它易于验证并暗示了此算法的正确性。

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

- Niklas B.

---

我认为你的意思是 A[k] ≤ A[j]。此外，如果你将 if 和 while 的主体放在自己的一行上，你的代码会更易读。除了细节之外：+1 - Walter Tross

@WalterTross：是的，你说得对，我已经更改了。我还添加了一些语法高亮 :) - Niklas B.

你可以使用数组和二分查找来进行快速查找。 - Deep

@Deep比摊销O(1)更快吗？;) 说真的，二分查找在这里没有帮助，因为您还需要删除元素，这需要与执行线性搜索相同的工作。 - Niklas B.

@WalterTross：你说得对，你可以加速算法。但它仍然是线性时间，所以最好保持简单，不要尝试常数优化。实际上，这可能几乎没有任何区别，因为二分查找可能不太高效，会导致分支预测错误等等。比较次数在最坏和平均情况下也是渐近相同的（O(n)）。 - Niklas B.

Answer 2

你可以使用栈，时间复杂度为O(N)。

算法: 从左侧开始向右移动。当你选择一个数组元素（假设为x）时，弹出栈直到栈中的元素（假设为y）有大于数组元素即x>y的元素。然后将该元素即x推入栈中。

例如：{40,50,11,32,55,68,75}。这里s是栈。

40，因为s为空，所以将其推入。 s: 40

50，因为s.peek() < 50，所以弹出40（40的更大元素是50），然后推入50。 s: 50

40的下一个更大元素是50。

11，s.peek() > 11，所以推入11。 s: 50, 11

32，s.peek() < 32，所以弹出元素，现在是50，它比32大，因此推入32。 s: 50, 32

11的下一个更大元素是32。

55，s.peek() < 55，所以弹出元素，即32，然后弹出50 < 55，然后推入55。 s: 55。

32的下一个更大元素是55。

50的下一个更大元素是55。

68，s.peek() < 68，所以弹出并推入68。 s: 68

75，s.peek() < 75，所以弹出并推入75 s:75。

68的下一个更大元素是75。

由于数组没有任何元素，只需弹出栈即可，表示所有数组中的元素都没有更大的元素，即-1。

75的下一个更大元素是-1。

相同算法的代码：

public static void fun(int[] a) {
    Stack<Integer> s = new Stack<Integer>();
    s.push(a[0]);

    for (int i = 1; i < a.length; i++) {
        if (s.peek() != null) {
            while (true) {
                if (s.peek() == null || s.peek() > a[i]) {
                    break;
                }
                System.out.println(s.pop() + ":" + a[i]);
            }
        }
        s.push(a[i]);
    }
    while (s.peek() != null) {
        System.out.println(s.pop() + ":" + -1);
    }
}

- Trying

---

我认为你还没有充分考虑清楚。你能否提供（即使是非常粗略的）伪代码来描述这个算法？ - Daniel Harms

我也认为这行不通。你需要在从左到右的迭代过程中维护整个单调递增子序列，因为一个位置的结果可能在该子序列的中间任何位置。 - Niklas B.

虽然我认为你的方法是正确的。它确实可以在O(n)的时间复杂度内运行。但是你的实现是错误的。 - Niklas B.

尽管你的实现有一些小错误，但算法是正确的。我一看到这个问题就想到了Niklas B的方法，没想到从左到右的循环也能行！ - Leo

没有点踩，但我猜可能是因为你的Java示例无法运行。 - Niklas B.