需要找到一个数组中的每个元素的下一个更大的元素

本文介绍了需要找到一个数组中的每个元素的下一个更大的元素的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

描述算法

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

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

如下9输入数组中

在大于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