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

题目描述
设计一个队列，除了支持常规的入队（enqueue）、出队（dequeue）操作外，还需要支持在O(1)时间复杂度内获取队列中的最小值。假设队列中存储的元素为整数，且队列操作合法（例如不会对空队列执行出队操作）。

解题思路分析
常规队列的入队和出队操作都是O(1)时间，但获取最小值需要遍历整个队列，时间为O(n)。为了实现O(1)时间获取最小值，可以借鉴“最小栈”的设计思想，但队列的先进先出特性使得直接套用栈的方法不可行。我们需要维护一个辅助数据结构，使其能够快速反映当前队列的最小值。

关键点：当元素入队时，它可能成为未来某个时刻的最小值；当元素出队时，如果它正好是最小值，需要快速更新最小值。
解决方案：使用一个双端队列（deque）作为辅助结构，维护一个“非递减”序列，保证队首始终是当前队列的最小值。

详细步骤

1. 数据结构定义

   • data_queue：普通队列（用链表或数组实现），用于存储所有元素。
   • min_deque：双端队列（deque），用于维护当前队列中的最小值候选序列。

2. 入队操作（enqueue）

   • 将新元素加入data_queue的尾部。
   • 处理min_deque：
     • 从min_deque的尾部开始，移除所有比新元素大的元素（因为这些元素在队列中比新元素早入队，但值更大，且新元素会比它们晚出队，所以它们不可能再成为最小值）。
     • 将新元素加入min_deque的尾部。
   • 时间复杂度：每个元素最多进入和离开min_deque一次，均摊O(1)。

   示例：
   初始队列：data_queue = [], min_deque = []
   入队3：data_queue = [3], min_deque = [3]
   入队1：data_queue = [3, 1], min_deque = [1]（移除3，因为1更小且更晚出队）
   入队2：data_queue = [3, 1, 2], min_deque = [1, 2]（2比1大，保留在尾部）

3. 出队操作（dequeue）

   • 从data_queue的头部移除元素。
   • 如果移除的元素等于min_deque的头部元素，说明当前最小值即将离开队列，因此也需要从min_deque的头部移除它。
   • 时间复杂度：O(1)。

   示例（接上一步）：
   出队：移除data_queue头部的3，但3不在min_deque头部（头部是1），所以min_deque不变。
   data_queue = [1, 2], min_deque = [1, 2]
   再次出队：移除1，它等于min_deque头部，所以同时移除min_deque头部的1。
   data_queue = [2], min_deque = [2]

4. 获取最小值（getMin）

   • 直接返回min_deque的头部元素。
   • 时间复杂度：O(1)。

5. 正确性保证

   • min_deque始终保持非递减序列，头部是当前队列的最小值。
   • 当元素入队时，移除min_deque尾部比它大的元素，确保min_deque中的元素是“潜在的最小值候选”。
   • 当元素出队时，仅当它是当前最小值时才从min_deque头部移除，避免提前丢失最小值信息。

代码实现（Python示例）

from collections import deque

class MinQueue:
    def __init__(self):
        self.data_queue = deque()  # 主队列
        self.min_deque = deque()   # 辅助双端队列，维护最小值候选
    
    def enqueue(self, x: int) -> None:
        self.data_queue.append(x)
        # 维护min_deque：从尾部移除比x大的元素
        while self.min_deque and self.min_deque[-1] > x:
            self.min_deque.pop()
        self.min_deque.append(x)
    
    def dequeue(self) -> int:
        if not self.data_queue:
            raise Exception("Queue is empty")
        val = self.data_queue.popleft()
        # 如果出队的元素是当前最小值，从min_deque头部移除
        if val == self.min_deque[0]:
            self.min_deque.popleft()
        return val
    
    def get_min(self) -> int:
        if not self.min_deque:
            raise Exception("Queue is empty")
        return self.min_deque[0]

复杂度分析

• 空间复杂度：O(n)，最坏情况下所有元素都存储在min_deque中。
• 时间复杂度：enqueue和dequeue操作均摊O(1)，getMin为O(1)。

总结
通过维护一个非递减的双端队列，我们实现了O(1)时间获取最小值的队列。关键思想是利用辅助结构记录“最小值候选”，并在入队和出队时动态更新这个候选序列。这种方法可以推广到其他需要快速获取队列极值的问题中。