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

题目描述
设计一个队列，除了支持队列的基本操作（入队、出队、查看队首元素）外，还需要支持在常数时间O(1)内获取队列中的最大值。

解题思路分析
这个题目是"最小栈"问题的队列版本扩展。栈具有后进先出(LIFO)的特性，可以方便地维护一个辅助栈来记录每个元素入栈时的最大值。但队列是先进先出(FIFO)的，当队首元素（最大值）出队后，我们需要知道剩余元素中的最大值，而单纯记录全局最大值是无法满足要求的。

我们需要一种能够动态追踪当前队列中最大值的方法。核心思路是使用一个双端队列（deque）作为辅助队列，来维护一个"递减"的序列，从而保证在O(1)时间内获取最大值。

详细步骤讲解

步骤1：理解核心数据结构
我们需要两个数据结构来配合工作：

1. 主队列 (data_queue)：一个普通的队列（可以用deque或Queue实现），用于存放所有元素，执行常规的入队、出队操作。
2. 辅助双端队列 (max_deque)：一个双端队列（必须用deque实现），用于动态维护一个"可能成为最大值"的候选元素序列。这个序列是非严格递减的（即允许相等元素相邻）。

步骤2：入队操作 (push / enqueue)
假设我们要将值 value 加入队列。

1. 主队列操作：将 value 加入到 data_queue 的末尾。
2. 辅助队列操作：这是关键步骤。我们需要维护 max_deque 的递减特性。
   • 从 max_deque 的末尾开始，将所有小于 value 的元素移除。因为这些元素在 value 之前进入队列，又比 value 小，所以只要 value 在队列中，它们就永远不可能成为最大值。
   • 将 value 加入到 max_deque 的末尾。

举例说明入队过程
假设依次入队：[5, 3, 4]

1. 入队 5:
   • data_queue: [5]
   • max_deque 为空，直接加入 -> [5]
2. 入队 3:
   • data_queue: [5, 3]
   • 比较：max_deque 末尾是5，5 > 3，所以不移除5，直接将3加入末尾 -> max_deque: [5, 3]
3. 入队 4:
   • data_queue: [5, 3, 4]
   • 从 max_deque 末尾开始比较：末尾是3，3 < 4，所以移除3。
   • 继续比较：现在末尾是5，5 > 4，停止移除。
   • 将4加入末尾 -> max_deque: [5, 4]
     此时，队列最大值是 max_deque 队首的5。

步骤3：获取最大值操作 (get_max)
这个操作非常简单直接：

• 返回 max_deque 的首元素即可。
• 因为我们在入队时保证了 max_deque 是一个递减序列，队首元素就是当前队列中的最大值。
• 时间复杂度：O(1)

步骤4：出队操作 (pop / dequeue)
假设我们要从队首移除一个元素。

1. 主队列操作：从 data_queue 的队首移除一个元素，记为 front_value。
2. 辅助队列操作：检查被移除的 front_value 是否等于 max_deque 的队首元素。
   • 如果相等：说明当前被移出主队列的元素正好是当前的最大值。因此，我们需要将 max_deque 的队首元素也移出。因为最大值已经不在主队列中了。
   • 如果不相等：说明被移出的元素不是最大值（它在 max_deque 中位于最大值之后，并且因为比某个值小，在入队时可能已经被移除了，或者它本身就不是候选者），那么 max_deque 不需要做任何操作。最大值保持不变。

继续举例说明出队过程
接上例，队列状态为：data_queue: [5, 3, 4], max_deque: [5, 4]

1. 第一次出队：
   • 从 data_queue 出队 5 -> data_queue: [3, 4]
   • 被出队的 5 等于 max_deque 的队首 5，所以也将 max_deque 的队首 5 出队 -> max_deque: [4]
   • 当前最大值为4。
2. 第二次出队：
   • 从 data_queue 出队 3 -> data_queue: [4]
   • 被出队的 3 不等于 max_deque 的队首 4，所以 max_deque 不变 -> max_deque: [4]
   • 当前最大值仍为4。

步骤5：查看队首元素 (peek)

• 直接返回 data_queue 的队首元素。
• 这个操作与最大值无关，是队列的基本操作。

复杂度分析

• 入队操作 (push)：虽然有时需要从 max_deque 尾部移除多个元素，但每个元素最多被加入和移出 max_deque 各一次，因此均摊时间复杂度是 O(1)。
• 出队操作 (pop)：只是比较和可能的移除队首操作，时间复杂度是 O(1)。
• 获取最大值 (get_max) 和 查看队首 (peek)：直接访问，时间复杂度是 O(1)。

代码实现（Python示例）

from collections import deque

class MaxQueue:

    def __init__(self):
        self.data_queue = deque()  # 主队列
        self.max_deque = deque()   # 辅助双端队列，用于维护最大值

    def max_value(self) -> int:
        """
        获取队列中的最大值
        """
        if not self.max_deque:
            return -1  # 或者根据题目要求返回特定值，如队列为空时
        return self.max_deque[0]

    def push_back(self, value: int) -> None:
        """
        入队操作
        """
        # 1. 元素加入主队列
        self.data_queue.append(value)
        # 2. 维护辅助双端队列的单调性（非严格递减）
        # 从尾部移除所有小于当前值的元素
        while self.max_deque and self.max_deque[-1] < value:
            self.max_deque.pop()
        # 3. 将当前值加入辅助队列尾部
        self.max_deque.append(value)

    def pop_front(self) -> int:
        """
        出队操作
        """
        if not self.data_queue:
            return -1  # 队列为空
        # 1. 从主队列出队
        front_value = self.data_queue.popleft()
        # 2. 如果出队的元素恰好是当前最大值，则辅助队列的队首也需要出队
        if front_value == self.max_deque[0]:
            self.max_deque.popleft()
        return front_value

    def peek_front(self) -> int:
        """
        查看队首元素（非必须，但常作为队列基本操作）
        """
        if not self.data_queue:
            return -1
        return self.data_queue[0]

总结
这个设计模式的核心在于利用一个单调的双端队列来高效地维护当前有效窗口（即整个队列）内的最大值候选者。它巧妙地处理了队列的FIFO特性带来的挑战。这种方法也是解决"滑动窗口最大值"等更复杂问题的基础。