11

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

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

4

3 回答 3

38

您可以使用堆栈，时间复杂度为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 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);
    }
}
于 2013-11-01T07:41:30.467 回答
3

您的问题的一个关键属性（在输入 32 的输出 55​​ 中看到）是，您显然只想要输入序列中给定输入元素之后的那些较大元素。否则此时的输出将是 40。

我建议你从右边处理数组，并维护一个可见元素的树（例如红黑树）。对于您处理的每个元素，您首先在 O(log n) 中搜索下一个较大元素的树。您将其存储在 O(1) 中以获得最后要打印的结果，然后将当前处理的元素插入到 O(log n) 中的树中。在 O(n log n) 中以这种方式处理所有元素，然后在 O(n) 中反转你必须输出的内容列表，你就完成了。

于 2013-11-01T07:10:46.410 回答
-4

This is easy:
1. Sort the array. O(n log n)
2. Find each element (index i) in the sorted array and pick element to the right or -1. Using binary search is O(log n), for each element it is O(n log n)

This could work (in 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]);
    }

Edit: This solution works if the requested result strictly requires the next higher element regardless of the relative ordering.

于 2013-11-01T07:09:09.657 回答