如何解决数组中的下一个更大的元素[不是第一个下一个更大的元素]向右？

Question

以前有一些帖子可以解决这个问题，但他们提供的解决方案是 右边的第一个下一个更大的元素，而不是 下一个更大的元素右边 .

假设输入数组是[4, 15, 2, 9, 20, 11, 13 ,16 ,3]

右边输出的下一个更大的元素是

4 -> 9 ,
15 -> 16 ,
2->3 ,
9->11 ,
20->-1 ,
11->13 ,
13->16 ,
16->-1 ,
3->-1 ,

第一个下一个更大的元素输出就像

4->15 ,
15->20 ,
2->9 ,
9->20 ,
20->-1
11->13
13-> 16
16-> -1
3-> -1

我希望你们已经明白其中的区别。

几乎所有在线资源[据我所知]都提供了第二种情况的解决方案。

我想要以乐观的方式解决第一种情况的[算法] [ < O(n^2) ]

任何类型的数据结构都适合我。

提前致谢。

Answer 1

这叫做超越者问题。它可以通过将项目以相反的顺序（即从最后到第一个）放入 self-balancing BST 来解决。将节点插入树中后，可以通过查看其右侧子树中的最小元素 child 来找到其下一个更大的元素，或者（如果它没有右侧 child），下一个更大的元素是该节点属于其左子树的第一个祖先（比插入节点大的第一个祖先）。

复杂度：O(n log n)

有一个替代解决方案使用类似于归并排序的 am 算法。

见

如何解决数组中的下一个更大的元素[不是第一个下一个更大的元素]向右？

How to solve the Next Greater Element in an array [ Not The First Next Greater Element] to the right?

arrays

algorithm

logic

stack

data-structures