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

题目描述
设计一个队列，该队列除了支持标准的入队（enqueue）和出队（dequeue）操作外，还需要支持在常数时间O(1)内获取队列中的最小值（getMin）。假设队列中存储的元素是可比较的（例如整数）。

解题思路分析
这个问题的难点在于，队列是先进先出（FIFO）的数据结构。当一个元素入队后，它会在队列中停留一段时间，直到所有在它之前入队的元素都出队后，它才会出队。如果我们简单地维护一个变量来记录当前最小值，那么当这个最小值元素被出队后，我们就需要知道新的最小值是谁，而这个新的最小值必须是队列中剩余元素里的最小值。由于元素是动态进出队列的，我们无法通过一次遍历（那将是O(n)时间复杂度）来找到新的最小值。

核心思路是使用两个栈来模拟一个队列，并利用“支持O(1)时间获取最小值的栈”的现有解法。

1. 基础组件：最小栈
   我们先回顾一个已解决的问题：实现一个支持O(1)时间获取最小值的栈。我们通常使用一个辅助栈（min_stack）来解决问题。主栈进行push和pop操作，辅助栈的栈顶始终保存着当前主栈中所有元素的最小值。

   • push(x): 将x压入主栈。同时，如果辅助栈为空，或者x小于等于辅助栈栈顶，则将x也压入辅助栈。
   • pop(): 弹出主栈栈顶元素。如果弹出的元素等于辅助栈栈顶，则也弹出辅助栈栈顶。
   • getMin(): 直接返回辅助栈的栈顶元素。

2. 用栈实现队列
   我们知道，用两个栈可以模拟一个队列。设这两个栈为stack_in和stack_out。

   • enqueue(x): 将所有入队元素都压入stack_in。
   • dequeue(): 如果stack_out为空，则将stack_in中的所有元素依次弹出并压入stack_out。然后从stack_out中弹出一个元素。如果stack_out不为空，则直接从stack_out弹出。

3. 组合方案：最小队列
   现在，我们将这两个思路结合起来。我们不再使用两个普通的栈，而是使用两个“最小栈”来分别作为stack_in和stack_out。每个最小栈自身都维护着其栈内元素的最小值。

   • MinQueue的结构：

     • stack_in: 一个最小栈，专门负责处理入队操作。
     • stack_out: 另一个最小栈，专门负责处理出队操作。

   • 关键点：队列的全局最小值，要么在stack_in中，要么在stack_out中。具体来说，它是stack_in的最小值和stack_out的最小值中更小的那个。因为队列中的所有元素，要么在stack_in里，要么在stack_out里。

循序渐进讲解

步骤一：定义“最小栈”类
首先，我们需要实现之前学过的最小栈，作为我们构建最小队列的基础模块。

class MinStack:
    def __init__(self):
        self.data_stack = []   # 主数据栈
        self.min_stack = []     # 辅助最小栈，栈顶保存当前最小值

    def push(self, x: int) -> None:
        # 元素压入主栈
        self.data_stack.append(x)
        # 如果辅助栈为空，或者新元素小于等于当前辅助栈栈顶（即当前最小值），则也压入辅助栈
        if not self.min_stack or x <= self.min_stack[-1]:
            self.min_stack.append(x)

    def pop(self) -> None:
        # 如果主栈为空，则无法弹出
        if not self.data_stack:
            return
        # 弹出主栈栈顶元素
        popped_value = self.data_stack.pop()
        # 如果弹出的这个值正好等于当前辅助栈栈顶（即当前最小值），则辅助栈也需要弹出
        if popped_value == self.min_stack[-1]:
            self.min_stack.pop()

    def top(self) -> int:
        # 获取主栈栈顶元素
        if not self.data_stack:
            return -1 # 或者抛出异常
        return self.data_stack[-1]

    def get_min(self) -> int:
        # 获取当前栈内最小值，即辅助栈栈顶
        if not self.min_stack:
            return -1 # 或者抛出异常
        return self.min_stack[-1]

步骤二：利用两个“最小栈”构建“最小队列”
现在，我们使用两个MinStack对象来构建我们的MinQueue。

class MinQueue:
    def __init__(self):
        self.stack_in = MinStack()  # 用于入队的栈
        self.stack_out = MinStack() # 用于出队的栈

    def enqueue(self, x: int) -> None:
        """入队操作"""
        # 所有新元素都压入 stack_in
        self.stack_in.push(x)

    def dequeue(self) -> None:
        """出队操作"""
        # 如果 stack_out 为空，需要将 stack_in 中的所有元素“倒入” stack_out
        if self.stack_out.get_min() == -1: # 或者用 len(self.stack_out.data_stack) == 0 判断是否为空
            while self.stack_in.get_min() != -1: # 当 stack_in 不为空时
                # 从 stack_in 弹出一个元素
                val = self.stack_in.top()
                self.stack_in.pop()
                # 将该元素压入 stack_out
                self.stack_out.push(val)
        # 从 stack_out 中弹出栈顶元素，即完成了出队
        self.stack_out.pop()

    def get_min(self) -> int:
        """获取队列中的最小值"""
        min_in = self.stack_in.get_min() # stack_in 中的最小值，如果栈为空，返回-1
        min_out = self.stack_out.get_min() # stack_out 中的最小值，如果栈为空，返回-1

        # 情况1: 两个栈都为空，队列为空
        if min_in == -1 and min_out == -1:
            return -1
        # 情况2: 只有 stack_in 有元素
        elif min_out == -1:
            return min_in
        # 情况3: 只有 stack_out 有元素
        elif min_in == -1:
            return min_out
        # 情况4: 两个栈都有元素，返回两者中更小的那个
        else:
            return min(min_in, min_out)

    # 通常队列还需要一个 front() 方法，获取队首元素（即下一个要出队的元素）
    def front(self) -> int:
        """获取队首元素但不出队"""
        # 原理同 dequeue，如果 stack_out 为空，需要倒入
        if self.stack_out.get_min() == -1:
            while self.stack_in.get_min() != -1:
                val = self.stack_in.top()
                self.stack_in.pop()
                self.stack_out.push(val)
        # 现在队首元素就是 stack_out 的栈顶
        return self.stack_out.top()

步骤三：复杂度分析

• 时间复杂度:

  • enqueue(x): O(1)。直接调用stack_in.push(x)。
  • dequeue(): 摊还时间复杂度为O(1)。虽然最坏情况下，当stack_out为空时，需要将stack_in中的所有元素移动到stack_out，这是一个O(n)的操作。但是，每个元素只会从stack_in被压入stack_out一次，也只会从stack_out弹出一次。因此，将一系列操作的总成本平均到每个操作上，dequeue的摊还成本是常数时间。
  • get_min(): O(1)。只是比较两个栈的最小值，是常数时间操作。
  • front(): 摊还时间复杂度为O(1)，原因同dequeue。

• 空间复杂度: O(n)。需要两个栈来存储所有元素，每个栈（包括其辅助栈）的空间消耗与元素数量n成线性关系。

总结
实现一个支持O(1)时间获取最小值的队列，其核心是“用栈实现队列”和“最小栈”两种思想的结合。通过维护两个最小栈（stack_in和stack_out），并保证队列的全局最小值是这两个栈各自最小值中的较小者，我们成功地满足了所有操作在常数或摊还常数时间内完成的要求。这是一个非常经典且巧妙的面试题，深刻考察了对栈和队列这两种基础数据结构特性的理解与灵活运用。