设计一个支持O(1)时间获取最小值的队列

题目描述
设计一个队列数据结构，除了常规的入队（enqueue）和出队（dequeue）操作外，还需要支持在O(1)时间复杂度内获取队列中的最小值（getMin）。要求所有操作的时间复杂度均为O(1)（平均或分摊情况下）。

解题思路
常规队列的入队和出队操作本身是O(1)的，但获取最小值需要遍历队列，时间复杂度为O(n)。为了实现O(1)获取最小值，可以借鉴最小栈（MinStack）的思想，使用双栈或双端队列（deque）来维护最小值信息。但队列的FIFO特性使得最小值维护更复杂，因为出队时可能移除当前最小值。解决方案是使用两个队列或一个队列加一个双端队列来动态维护最小值。

步骤详解

1. 数据结构设计

   • 使用一个普通队列dataQueue存储所有元素。
   • 使用一个双端队列minDeque（或另一个队列）来维护可能的最小值序列，确保队首始终是当前队列的最小值。
   • 例如：队列元素为[3, 1, 2]时，minDeque应存储[1, 2]（因为1是当前最小，2在1之后可能成为未来最小值）。

2. 入队操作（enqueue）

   • 将新元素x加入dataQueue。
   • 维护minDeque：
     • 从minDeque尾部开始，移除所有比x大的元素（因为这些元素在x之后出队，不可能成为最小值）。
     • 将x加入minDeque尾部。
   • 时间复杂度：每个元素最多进入和离开minDeque一次，分摊O(1)。
   • 示例：依次入队3, 1, 2
     • 入队3：dataQueue = [3], minDeque = [3]
     • 入队1：移除minDeque中的3（因为3>1），加入1 → minDeque = [1]
     • 入队2：minDeque尾部1<2，直接加入2 → minDeque = [1, 2]

3. 出队操作（dequeue）

   • 若dataQueue为空，报错。
   • 否则，弹出dataQueue队首元素y。
   • 若y等于minDeque队首元素，说明当前最小值被移出，同时弹出minDeque队首。
   • 时间复杂度：O(1)。
   • 示例：接上文，出队操作：
     • 出队3：dataQueue = [1, 2], minDeque队首为1≠3，不操作 → minDeque保持[1, 2]
     • 出队1：dataQueue = [2], minDeque队首1=1，弹出minDeque队首 → minDeque = [2]

4. 获取最小值（getMin）

   • 直接返回minDeque的队首元素（若队列非空）。
   • 时间复杂度：O(1)。

5. 正确性分析

   • minDeque始终保持非严格递增序列（队首最小），且队首对应dataQueue中的当前最小值。
   • 当最小值出队时，minDeque同步移除该值，下一个队首即为新的最小值。
   • 由于每个元素仅出入minDeque一次，所有操作的分摊时间复杂度为O(1)。

代码实现（Python示例）

from collections import deque

class MinQueue:
    def __init__(self):
        self.dataQueue = deque()  # 主队列
        self.minDeque = deque()   # 辅助双端队列，维护最小值

    def enqueue(self, x: int) -> None:
        self.dataQueue.append(x)
        # 维护minDeque：移除尾部比x大的元素
        while self.minDeque and self.minDeque[-1] > x:
            self.minDeque.pop()
        self.minDeque.append(x)

    def dequeue(self) -> int:
        if not self.dataQueue:
            raise Exception("Queue is empty")
        y = self.dataQueue.popleft()
        if y == self.minDeque[0]:
            self.minDeque.popleft()
        return y

    def getMin(self) -> int:
        if not self.minDeque:
            raise Exception("Queue is empty")
        return self.minDeque[0]

总结
通过结合队列和双端队列，利用“未来最小值”的单调性，在O(1)时间内动态维护最小值。此方法适用于需要快速获取最值的流式数据处理场景（如滑动窗口最大值/最小值问题）。