用右边的下一个更高的数字替换每个数字，a[i]，
用右边的下一个更高的数字替换每个数字，a[i]，
提问于 2014-01-05 19:06:23
给定一个整数数组，将每个数字ai替换为其右侧的下一个更高的数字(根据值)，其值更接近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)。
有没有针对这一点的优化方法？
回答 1
Stack Overflow用户
发布于 2014-01-05 20:55:02
您可以为整个数字列表构建平衡的BST。然后，再次遍历列表，使用树查找下一个较大的数字。完成每个项目后，将其从树中删除。
树的深度永远不会增加，因此首先构建树的总复杂度为O( never )，查找下一个最大项的总复杂度为O(log )，删除当前项的总复杂度为O(log )。总体O(n log n)，没有花哨的数据结构。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/20932815
复制相关文章
相似问题
腾讯云开发者
