c++ - 一种保持元素有序的数据结构，支持快速插入和计算连续元素之间的最大差值

Question

我可以将元素存储在 STL 集中，用于 O(logN) 插入和计算 O(NlogN) 中的最大连续差异。有没有更快的方法来做到这一点。我不要代码。只是实现此 DS 的一些想法。感谢您的帮助。

Answer 1

只需围绕 STL 集编写一个包装器。每次插入时，在插入之后，获取下一个最高键并计算差值。如果它大于当前最大值，则替换它并存储加起来达到该最大值的键。

插入仍然是 O(log n)。获得最大值将是 O(1)。

删除键时，查看它是否在计算最大差异时使用的键之一。如果是，则必须使最大值无效，然后找到新的最大值。只需按排序顺序遍历所有元素，并保持运行最大值。到迭代结束时，您将知道 O(n) 中的最大值。

所以删除在最坏的情况下需要 O(n)。