Linkedlist在恒定时间内跟踪min？

Question

编辑:

这并不像你想象的那么简单.考虑这样一个事实,即每增加一个新号码都会从链表中推出一个旧数字.

解决方案似乎并不像使用变量跟踪最小数字那么简单.如果最小值被推出链表怎么办？那又怎样？你怎么知道新的分钟是什么？

我听到了这个采访问题:

你有一个固定长度的链表.

• 在时间t = 0,链表被填充随机数.

• 在每个时间增量中,一个新数字被馈送到链表的头部,并且一个数字从尾部推出.

• 在第一个时间间隔之前,您只允许进行一次遍历.

  • 这意味着一次遍历.每次都不是一次.
    .

• O(1)存储.

您的任务是能够在每次交互时返回链表的最小值.

什么算法能够做到这一点？

---

有趣的说明:

由于没有关于时间复杂度的信息,因此您可以使用排序操作.那么唯一的问题是:排序需要多次迭代.

Answer 1

在有人误解我的帖子并向其投票之前澄清.

第一,

O(1)存储与单个寄存器不同.这意味着不断的空间使用.

第二,

我将把你的LL称为一个恒定大小的队列(CSQ).

初始化队列时,还要初始化一个最小堆,其中队列的所有元素都保留对应于它们的堆节点的引用(指针).

关于CSQ的1个操作

• 在CSQ的O(1)时间内弹出1个元素.
• 在O(lg n)时间内从最小堆中删除相应的节点.
• 在O(lg n)时间内将相应的元素添加到最小堆.
• 在O(1)时间内将1个元素推入CSQ,并标记对上面添加的堆节点的引用.

上述操作保证堆大小始终与队列大小保持同步 - 因此O(1).我采用一个遍历限制意味着它必须比简单的O(n)搜索更优化.这是O(lg n).

寻找分钟

显然是O(1).只需返回最小堆的头部.