arrays - 将每个数字 a[i] 替换为其右侧的下一个更高的数字，

Question

给定一个整数数组，将每个数字 a[i] 替换为其右侧的下一个更高的数字(根据值)，其值更接近 a[i] (如果不存在则保持原样.)

例如

输入->3 7 5

输出 -> 5 7 5

输入 –> 3 6 2 6 4 7 1

输出-> 4 7 4 7 7 7 1

这个问题是在面试中被问到的。

如果从右边开始，将每个元素插入到 BST 中，然后在 BST 中找到更接近的值，但这种方法在最坏的情况下也是 O(n^2)。

有什么优化方法吗？

Answer 1

您可以为整个数字列表构建一个平衡的 BST。然后，再次遍历列表，使用树找到下一个更大的数字。每项完成后，将其从树中移除。

树的深度永远不会增加，所以首先构建树的总复杂度为 O(n log n)，为找到下一个最大的项目每个项目的 O(log n)，以及 O(log n ) 用于删除当前项目。总体 O(n log n)，没有花哨的数据结构。