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

Question

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

复杂性应该小于O(n^2).您可以使用数据结构而不限制空间复杂性.

Answer 1

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

算法:
从左侧开始向右移动.当你从数组中选择一个元素时(比方说x),弹出Stack直到Stack中的元素(比如y)有一个大于数组元素的元素,即x> y.然后将元素即x推到堆叠.

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

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

50,因为s.peek()<50所以pop 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 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);
    }
}

Answer 2

这很简单：
1. 对数组进行排序。O(n log n)
2. 查找已排序数组中的每个元素（索引 i）并选择右侧的元素或 -1。使用二分查找的时间复杂度为 O(log n)，对于每个元素来说，时间复杂度为 O(n log n)

这可以工作（在 C# 中）：

    IEnumerable<int> NextNumber (int[] numbers)
    {
        var sorted = numbers.OrderBy(n => n).ToList();
        int cnt = numbers.Count()-1;
        return numbers.Select(sorted.BinarySearch).Select(i => i == cnt ? -1 : sorted[i + 1]);
    }

编辑：如果请求的结果严格要求下一个更高的元素（无论相对顺序如何），则此解决方案有效。