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

Question

我正在自学一门算法课程,我正在尝试解决以下问题:

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

Insert(x):删除不大于x的所有元素,并将x添加到集合中.
FindMin():找到set的最小值.

我知道,一旦你有了Insert,findmin会变得微不足道,看看如何使用链表实现,你可以同时删除多个元素(即O(1)),但找出要删除的链接(也就是x去的地方)似乎像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.因此,插入是摊销O(1).

希望这可以帮助!