为每个元素在数组中查找下一个更高的元素 [英] Find next higher element in an array for each element

问题描述

从给定的输入数组中，对于每个元素，找到每个数组中存在的下一个更高的元素.例如 {40,50,11,32,55,68,75} 输出应该是 {50,55,32,55,68,75,-1}.对于元素，如果不存在更高的元素，则打印 -1.

From a given input array, for each element, find next higher element present in each array. For example {40,50,11,32,55,68,75} output should be {50,55,32,55,68,75,-1}. For element if no higher element is present, print -1.

复杂度应该小于O(n^2).您可以使用数据结构，并且不受空间复杂度的限制.

Complexity should be less than O(n^2). You can use data structures and no constraint on space complexity.

推荐答案

可以使用Stack，时间复杂度为O(N).

You can use a Stack and the time complexity is O(N).

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

The algorithm:
Start from the left side and move towards the right. When you pick an element from the array (let's say x), pop the Stack until the elements from the Stack (lets say y) has an element greater than the array element i.e. x> y. Then push the element i.e. x to stack.

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

e.g. {40,50,11,32,55,68,75} . here s is stack.

40，因为 s 是空的推动它.s: 40

40, as s is empty push it. s: 40

50，如 s.peek() <50 所以弹出 40(40 的大元素是 50)然后推送 50.s: 50

50, as s.peek() < 50 so pop 40 (40's greater element is 50) then push 50. s: 50

40 - 50 的下一个更高的元素.

Next higher element of 40 - 50.

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

11, s.peek() > 11 so push 11. s: 50, 11

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

32, s.peek() < 32, so pop the element and now it's 50 which is greater than 32 hence push 32. s: 50 ,32

11 - 32 的下一个更高的元素.

Next higher element of 11 - 32.

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

55, s.peek() < 55, so pop the element i.e. 32 then pop next as well as 50 < 55, then push 55. s: 55.

32 - 55 的下一个更高的元素.

Next higher element of 32 - 55.

50 - 55 的下一个更高的元素.

Next higher element of 50 - 55.

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

68, s.peek() < 68 so pop it and push 68. s: 68

75, s.peek() <75 所以弹出它并推送 75 s:75.

75, s.peek() < 75 so pop it and push 75 s:75.

68 - 75 的下一个更高的元素.

Next higher element of 68 - 75.

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

As the array does not have any element no just pop the stack say that for all the elements inside the array does not have greater element i.e. -1.

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);
    }
}

这篇关于为每个元素在数组中查找下一个更高的元素的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！