需要找到一个数组中的每个元素的下一个更大的元素 [英] Need to find the next greater element of every element in an array

问题描述

描述算法

有关的输入阵列中的每个元素，相应的输出是下面的输入元件的第一个数字，那就是高于输入元素

For each element in the input array, the corresponding output is the first number that follows the input element, that is greater than the input element.

在换句话说，对于给定的输入[I]，输出[i]为一些元件输入[j]的其中j是最小索引使得J>时i和输入[J]>输入[I]

In other words, for a given input[i], the output[i] is some element input[j] where j is the minimum index such that j > i and input[j] > input[i]

示例

Input  12 15 22  9  7  2 18 23 27 
Output 15 22 23 18 18 18 23 27 -1

例如，对应于9的输出为18，因为图18是符合这些要求的阵列中的第一个数字

For example, the output that corresponds to 9 is 18 since 18 is the first number in the array that meets these requirements

1. 如下9输入数组中
2. 在大于9

问题

任何人都可以给我建议的算法为O更好的（N ^ 2）？

Can anyone suggest me an algorithm better than O(n^2)?

推荐答案

一种方法是使用一个堆栈，其中在堆叠的每个条目是一个值：索引对。遍历输入数组，从堆栈，其值是小于当前项的输入数组中的值弹出的项目。索引对入堆栈：一旦所有的小值已经从堆栈中弹出，电流值推。当到达输入数组的末尾，栈中的任何剩余的数据项得到的-1的输出值，以指示没有更大数目被发现。

One approach is to use a stack, where each entry in the stack is a value:index pair. Iterate through the input array, popping items from the stack whose value is less than the value of the current item in the input array. Once all of the smaller values have been popped from the stack, push the current value:index pair onto the stack. When the end of the input array is reached, any remaining entries in the stack get an output value of -1 to indicate that no larger number was found.

使用问题的例子，这里的算法将如何工作。

Using the example in the question, here's how the algorithm would work

input item 12
    stack = 12:0

input item 15
    pop 12:0 and set output[0] = 15
    stack = 15:1

input item 22
    pop 15:1 and set output[1] = 22
    stack = 22:2

input item 9
    stack = 9:3, 22:2

input item 7
    stack = 7:4, 9:3, 22:2

input item 2
    stack = 2:5, 7:4, 9:3, 22:2

input item 18
    pop 2:5 and set output[5] = 18
    pop 7:4 and set output[4] = 18
    pop 9:3 and set output[3] = 18
    stack = 18:6, 22:2

input item 23
    pop 18:6 and set output[6] = 23
    pop 22:2 and set output[2] = 23
    stack = 23:7

input item 27
    pop 23:7 set output[7]= 27
    stack = 27:8

end of array
    pop 27:8 and set output[8] = -1
    done

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