data-structures - 在 O(1) 时间内删除集合中小于或等于 x 的所有元素的数据结构

Question

我正在自学算法类(class)，我正在尝试解决以下问题:

描述一个数据结构来存储一组实数，它可以在 O(1) 的摊销时间内执行以下每个操作:

Insert(x) : 删除所有不大于 x 的元素，并将 x 添加到集合中。
FindMin() : 求集合的最小值。

我意识到一旦你有了 Insert，findmin 就变得微不足道了，看看如何使用链表实现，你可以同时删除多个元素(即 O(1))，但找出要删除的链接(也就是 x go) 看起来像 O(n) 或 O(log n) 操作，而不是 O(1)。问题给出了提示:考虑使用堆栈，但我看不出这有什么帮助。

感谢任何帮助。

原问题如下:

Answer 1

请注意，您的目标是获得 O(1) 摊销 时间，而不是 O(1) 时间。这意味着只要 n 次操作不超过 O(n) 时间，您就可以在每次操作中做尽可能多的工作。

这是一个简单的解决方案。将元素按升序存储在堆栈中。要插入一个元素，请不断弹出堆栈，直到它为空或顶部元素大于 x，然后将 x 压入堆栈。要执行 find-min，请读取堆栈顶部。

Find-min 显然在 O(1) 时间内运行。现在让我们看看插入。直观地说，每个元素最多被推送和弹出一次，因此我们可以将昂贵插入的工作分散到更便宜的插入中。更正式地说，设势为 n，即堆栈上的元素数。每次插入时，都会进行一些弹出次数(例如 k)，并且潜在增加 1 - k(添加一个新元素，删除 k)。那么摊销成本是 k + 1 + 1 - k，即 2。因此，insert 的摊销成本为 O(1)。

希望这会有所帮助!