实现一个支持O(1)时间获取最大值的队列

题目描述
设计一个队列，除了支持队列的基本操作（enqueue、dequeue）外，还需要在常数时间内获取队列中的最大值元素。

解题思路分析
这个题目是"最小栈"问题的扩展，但难度更高。队列的先进先出特性使得最大值维护变得复杂，因为当队首元素出队时，如果它正好是当前最大值，我们需要快速知道剩余元素中的最大值。

核心思路：使用双端队列维护最大值
我们可以使用一个辅助双端队列来维护当前队列中的最大值候选序列。

实现步骤

1. 数据结构设计

   • 使用一个普通队列dataQueue存储实际数据
   • 使用一个双端队列maxQueue存储可能成为最大值的元素（按递减顺序排列）

2. 入队操作（enqueue）

   • 将新元素加入dataQueue
   • 维护maxQueue：从尾部开始，移除所有小于当前值的元素，然后将新元素加入尾部
   • 这样保证maxQueue头部始终是当前最大值

3. 出队操作（dequeue）

   • 从dataQueue头部移除元素
   • 如果移除的元素等于maxQueue头部元素，则同时从maxQueue头部移除
   • 这样确保maxQueue头部始终是当前队列中的最大值

4. 获取最大值（getMax）

   • 直接返回maxQueue头部的元素

具体实现示例

from collections import deque

class MaxQueue:
    def __init__(self):
        self.dataQueue = deque()  # 存储实际数据的队列
        self.maxQueue = deque()   # 存储可能最大值的双端队列
    
    def enqueue(self, value: int) -> None:
        # 新元素加入主队列
        self.dataQueue.append(value)
        
        # 维护最大值队列：移除所有小于当前值的元素
        while self.maxQueue and self.maxQueue[-1] < value:
            self.maxQueue.pop()
        
        # 将新元素加入最大值队列
        self.maxQueue.append(value)
    
    def dequeue(self) -> int:
        if not self.dataQueue:
            raise Exception("Queue is empty")
        
        # 从主队列头部移除元素
        value = self.dataQueue.popleft()
        
        # 如果移除的是当前最大值，也从最大值队列中移除
        if value == self.maxQueue[0]:
            self.maxQueue.popleft()
        
        return value
    
    def getMax(self) -> int:
        if not self.maxQueue:
            raise Exception("Queue is empty")
        return self.maxQueue[0]

时间复杂度分析

• 入队操作：虽然内层有循环，但每个元素最多被处理两次（一次入队一次出队），均摊时间复杂度为O(1)
• 出队操作：O(1)
• 获取最大值：O(1)

示例演示
操作序列：enqueue(1) → enqueue(3) → enqueue(2) → getMax() → dequeue() → getMax()

执行过程：

1. enqueue(1): dataQueue = [1], maxQueue = [1]
2. enqueue(3): dataQueue = [1,3], maxQueue移除1加入3 → [3]
3. enqueue(2): dataQueue = [1,3,2], maxQueue = [3,2]
4. getMax(): 返回3
5. dequeue(): 移除1，dataQueue = [3,2]，1≠3，maxQueue不变
6. getMax(): 返回3

关键理解点

• maxQueue维护的是一个递减序列，头部始终是当前最大值
• 当新元素入队时，它会让所有比它小的元素"失效"
• 只有当最大值出队时，我们才需要更新maxQueue

这种设计巧妙地利用了队列的先进先出特性，通过维护一个候选最大值序列，实现了O(1)时间复杂度的最大值获取。