algorithm - 为每个元素在数组中查找下一个更高的元素

Question

<分区>

Answer 1

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

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

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

40，因为s是空的push它。 s: 40

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

Next higher element of 40 - 50.

11, s.peek() > 11 所以按 11。s: 50, 11

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

Next higher element of 11 - 32.

55，s.peek() < 55，所以弹出元素，即 32 然后弹出下一个以及 50 < 55，然后推送 55。s: 55。

Next higher element of 32 - 55.

Next higher element of 50 - 55.

68, s.peek() < 68 所以弹出它并按下 68。s: 68

75，s.peek() < 75 所以弹出它并按下 75 s:75。

Next higher element of 68 - 75.

由于数组没有任何元素，所以不只是弹出堆栈说对于数组内的所有元素都没有更大的元素，即-1。

Next higher element of 75 - -1.

代码中的相同算法:

public static void getNGE(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);
    }
}