java - 从队列中获取 O(1) 时间内的最小值/最大值？

Question

<分区>

Answer 1

存在这样一种结构，它的作用类似于队列，但可以让您在恒定时间内检索最小/最大值，实际上并不是严格恒定的，它是摊销的恒定时间(如您所猜，称为最小/最大队列)。有两种实现方式——使用两个堆栈或使用一个队列和一个双端队列。

Deque 实现看起来更不像这样(与语言无关):

所以我们有一个最大元素的双端队列，前面的那个是所需的最大值，还有一个标准队列。

推送操作

1. 如果队列为空，只需将元素压入队列和双端队列。
2. 如果队列不为空，将元素压入队列，从双端队列的后面删除所有严格小于我们现在压入的元素的元素(它们肯定不是最大值，因为压入元素更大，将在队列中持续更长时间)并将当前元素推到双端队列的后面

删除操作

1. 如果双端队列的前端等于队列的前端，则将两者都弹出(双端队列从前端开始)
2. 如果双端队列的前端不等于队列的前端，则只弹出队列，弹出的元素肯定不是最大的。

获取最大值

1. 它只是双端队列的第一个元素。

(应该添加很多参数来阐明它为什么有效，但下面给出的第二个版本可能是对这种必要性的回答)

Stack 的实现非常相似，我认为实现起来可能会稍微长一些，但也许更容易掌握。首先要注意的是，将最大元素存储在堆栈中很容易 - 简单练习(对于懒惰的人 - Stack with find-min/find-max more efficient than O(n)? )。第二部分，如果第一次看到可能有点棘手，那就是使用两个堆栈实现队列非常容易，可以在这里找到 - How to implement a queue using two stacks? .基本上就是这样——如果我们能得到两个堆栈的最大元素，我们就能得到整个队列的最大元素(如果你想要一个更正式的论点，取最大值是关联的或类似的东西，但我敢打赌你不会'，这真的很明显)。

最小版本是类比完成的。

一切也可以在 O(nlogn) 时间内使用一个集合(或类似的东西)完成，但这是毫无意义的，因为 O(n) 中的常量非常小，它应该更快，但易于实现.

第一个版本中不感兴趣的部分:

希望我能帮上一点忙。并希望没有说错任何话。如果需要，可以用 C++/C 给出一个简单的实现。如果您对表格有任何反馈，我将不胜感激，因为这是我在任何地方发表的第一篇此类文章 :)(英语不是我的母语)。另外，对正确性进行一些确认也很好。

编辑:因为这个答案让我得到了一些分数，我觉得有必要稍微清理一下，也稍微扩展一下。