实现一个支持O(1)时间获取最大值的队列
题目描述
设计一个队列，除了支持基本的队列操作（入队、出队、查看队首元素）外，还需要在O(1)时间内获取队列中的最大值。假设队列中的元素为整数。
解题思路
如果只是实现普通队列，可以使用链表或数组，但获取最大值需要遍历整个队列，时间复杂度为O(n)。为了在O(1)时间内获取最大值，我们需要维护一个额外的数据结构来记录当前队列中的最大值。这里的关键在于：当入队一个新元素时，它可能成为未来的最大值；当出队一个元素时，如果这个元素恰好是当前最大值，我们需要知道下一个最大值是谁。
解决方案：使用双端队列辅助
我们可以使用一个主队列（普通队列）来存储所有元素，同时使用一个双端队列（deque）来维护一个“最大值候选序列”。这个双端队列中的元素是单调递减的，队首元素就是当前队列的最大值。
详细步骤
-
数据结构定义
queue: 用于存储所有元素的普通队列（使用链表或数组实现）。maxDeque: 一个双端队列（deque），用于维护当前队列中的最大值候选序列，保持单调递减。
-
入队操作（push）
- 将新元素加入主队列的尾部。
- 处理双端队列：
- 从双端队列的尾部开始，移除所有比新元素小的元素（因为这些元素在新元素加入后不可能再成为最大值）。
- 将新元素加入双端队列的尾部。
- 时间复杂度：虽然看起来有循环，但每个元素最多被加入和移除双端队列一次，因此均摊时间复杂度为O(1)。
-
出队操作（pop）
- 如果主队列为空，则抛出异常。
- 从主队列头部移除元素。
- 如果移除的元素等于双端队列头部的元素（即当前最大值），则同时从双端队列头部移除该元素。
- 时间复杂度：O(1)。
-
获取最大值（getMax）
- 如果双端队列不为空，返回其头部元素。
- 如果队列为空，抛出异常。
- 时间复杂度：O(1)。
-
查看队首元素（peek）
- 返回主队列的头部元素。
- 时间复杂度：O(1)。
示例演示
假设依次执行以下操作：
push(1), push(3), push(2), getMax(), pop(), getMax()
-
push(1):
主队列: [1]
maxDeque: [1]（初始加入） -
push(3):
主队列: [1, 3]
maxDeque: 从尾部移除1（因为1<3），加入3 → [3] -
push(2):
主队列: [1, 3, 2]
maxDeque: 2<3，直接加入2 → [3, 2]（单调递减） -
getMax(): 返回maxDeque队首3
-
pop(): 主队列队首1出队，但1≠3，maxDeque不变
主队列: [3, 2]
maxDeque: [3, 2] -
getMax(): 返回maxDeque队首3
边界情况处理
- 队列为空时，出队或获取最大值应抛出异常。
- 如果存在多个相同最大值，maxDeque中应保留多个相同值（或存储索引区分），确保出队时不会提前移除最大值。
代码实现要点（伪代码）
class MaxQueue:
def __init__(self):
self.queue = collections.deque() # 主队列
self.maxDeque = collections.deque() # 辅助双端队列
def push(self, value):
self.queue.append(value)
while self.maxDeque and self.maxDeque[-1] < value:
self.maxDeque.pop()
self.maxDeque.append(value)
def pop(self):
if not self.queue:
raise Exception("Queue is empty")
val = self.queue.popleft()
if val == self.maxDeque[0]:
self.maxDeque.popleft()
return val
def getMax(self):
if not self.maxDeque:
raise Exception("Queue is empty")
return self.maxDeque[0]
def peek(self):
if not self.queue:
raise Exception("Queue is empty")
return self.queue[0]
总结
通过维护一个单调递减的双端队列，我们确保了最大值始终在maxDeque的头部。这种方法的每个操作均摊时间复杂度为O(1)，空间复杂度为O(n)，是一种经典的以空间换时间的解法。