为每个数组元素找到下一个更高的元素

Question

为每个数组元素找到下一个更高的元素

algorithmdata-structures

11

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

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

- AKS

1

如果您对这个数组使用归并排序O(nlogn)，它不会起作用吗？ - aked

1

@dekdev- 你应该把那个发表为答案。 :-) - templatetypedef

2

你的意思是 http://www.geeksforgeeks.org/next-greater-element/ 吗？你的例子没有区分下一个更高和右侧的下一个更高。 - Deepak

@Deepak，我认为AKS的问题是错误的。我正在删除我的答案。 - aked

@dekdev，那是对他所问问题的很好的回答。 - Deepak

显示剩余3条评论

3个回答

3

您的问题的一个关键特性，如输入32的输出55中所见，是您仅想要那些在输入序列中给定输入元素之后的更大元素。否则，在该点处的输出将为40。

我建议您从右侧处理数组，并维护已看到元素的树（例如红黑树）。对于每个要处理的元素，您首先以O（log n）搜索下一个较大的元素。您将其存储为O（1），以便在最后打印要输出的结果，然后在O（log n）中将当前处理的元素插入树中。以这种方式处理所有元素的时间复杂度为O（n log n），然后在O（n）中反转您需要输出的事物列表，完成操作。

- MvG

投票负者，愿意发表评论吗？ - MvG

给你的回答点赞。这是一个非常棒的方法。 - CuriousCoder

除非我误解了你的意思，否则你的算法没有考虑元素位置，只是考虑值在数组中给定值之后出现的事实。然而，我认为原始问题是关于找到第一个在数组位置上大于给定值且在给定值之后出现的值。 - Dmitry Aleks

举个具体的例子，对于以下数组： 5 8 7 期望的输出如下： 8 -1 -1 而你的解决方案将导致： 7 -1 -1 @Trying 提出的算法产生了正确的结果。 - Dmitry Aleks

-4

这很简单：
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]);
    }

编辑：如果所请求的结果严格要求下一个更高的元素，而不考虑相对顺序，则此解决方案有效。

- alzaimar

1

我认为原始数组中元素的相对顺序很重要。看看原始问题以及32会发生什么。 - templatetypedef

我一开始认为这是一个错误，但你是正确的。我会修改我的建议。 - alzaimar

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Trying · Accepted Answer

您可以使用栈，时间复杂度为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（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);
    }
}