在每个元素的数组中找到下一个更高的元素 [英] 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）时，弹出Stack（堆栈），直到Stack的元素（让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 是堆栈。

40，因为s是空的。 s：40

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

50，as 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 so push 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然后接下来流行， 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屋！