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

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

解题思路分析
这个问题的难点在于队列是先进先出（FIFO）的结构，当元素出队时，如果出队的元素正好是当前的最小值，我们需要快速知道剩余元素中的最小值是谁。单纯用一个变量记录最小值是不够的，因为当最小值出队后，我们无法快速知道次小值。

核心思路是使用一个辅助的双端队列（Deque）来动态维护当前队列中的“潜在最小值序列”。这个辅助队列的队首元素始终是当前主队列中的最小值。

详细步骤讲解

1. 数据结构设计

   • 主队列（mainQueue）：使用普通的队列（如LinkedList）来存储所有元素，实现正常的FIFO操作。
   • 辅助双端队列（minDeque）：使用双端队列（如ArrayDeque），它内部维护一个“非严格递增”的序列。这个序列的特点是，队首元素永远是当前主队列中的最小值，并且序列中的元素是递增的。

2. 入队操作（enqueue）

   • 新元素首先加入主队列的尾部。
   • 处理辅助队列：
     • 从辅助队列的尾部开始，将所有比新元素大的元素移除。因为新元素比它们小，且会比它们更晚出队（FIFO原则），所以那些比新元素大的元素在后续就不可能再成为最小值了。
     • 将新元素加入到辅助队列的尾部。
   • 时间复杂度：虽然看起来有循环，但每个元素最多被加入和移除辅助队列各一次，所以均摊时间复杂度是O(1)。

   示例：依次入队 3, 1, 2

   • 入队3：主队列[3]，辅助队列[3]（最小值3）
   • 入队1：主队列[3, 1]。辅助队列尾部3>1，移除3，加入1。辅助队列变为[1]（最小值1）
   • 入队2：主队列[3, 1, 2]。辅助队列尾部1<2，直接加入2。辅助队列变为[1, 2]（最小值1）。因为1在2之前，且1<2，所以1出队前，最小值始终是1。

3. 出队操作（dequeue）

   • 检查主队列的队首元素是否等于辅助队列的队首元素。
     • 如果相等，说明出队的元素就是当前最小值。那么辅助队列的队首也需要出队，因为它已经不在主队列中了。
     • 如果不相等，直接出队主队列队首即可，不影响当前最小值。
   • 时间复杂度：O(1)。

   接上例：主队列[3, 1, 2]，辅助队列[1, 2]，最小值1。

   • 出队：主队列队首3 ≠ 辅助队列队首1。主队列变为[1, 2]，辅助队列不变，最小值仍为1。
   • 再次出队：主队列队首1 = 辅助队列队首1。主队列变为[2]，辅助队列队首1出队，变为[2]，最小值变为2。

4. 获取队首元素（getFront）

   • 直接返回主队列的队首元素。
   • 时间复杂度：O(1)。

5. 获取最小值（getMin）

   • 直接返回辅助队列的队首元素。
   • 时间复杂度：O(1)。

代码实现（Java）

import java.util.LinkedList;
import java.util.Deque;
import java.util.Queue;

public class MinQueue {
    private Queue<Integer> mainQueue;
    private Deque<Integer> minDeque;

    public MinQueue() {
        mainQueue = new LinkedList<>();
        minDeque = new LinkedList<>();
    }

    public void enqueue(int value) {
        // 新元素加入主队列
        mainQueue.offer(value);
        // 维护辅助双端队列：移除尾部所有比新元素大的元素
        while (!minDeque.isEmpty() && minDeque.peekLast() > value) {
            minDeque.pollLast();
        }
        // 将新元素加入辅助队列尾部
        minDeque.offerLast(value);
    }

    public int dequeue() {
        if (mainQueue.isEmpty()) {
            throw new RuntimeException("Queue is empty");
        }
        int frontValue = mainQueue.poll();
        // 如果出队的元素正好是当前最小值，则辅助队列的队首也需要出队
        if (frontValue == minDeque.peekFirst()) {
            minDeque.pollFirst();
        }
        return frontValue;
    }

    public int getFront() {
        if (mainQueue.isEmpty()) {
            throw new RuntimeException("Queue is empty");
        }
        return mainQueue.peek();
    }

    public int getMin() {
        if (minDeque.isEmpty()) {
            throw new RuntimeException("Queue is empty");
        }
        return minDeque.peekFirst();
    }
}

关键点总结

• 辅助双端队列 minDeque 维护的是一个“非严格递增”的序列，队首永远是最小值。
• 入队时，从尾部移除比新元素大的元素，是为了保证序列的递增性，并淘汰掉那些“永无出头之日”的较大值。
• 出队时，只有当主队列队首等于辅助队列队首（即当前最小值）时，才需要将辅助队列的队首出队。
• 所有操作（入队、出队、获取队首、获取最小值）的均摊时间复杂度都是O(1)，空间复杂度是O(n)。