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

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

解题思路
队列的特点是先进先出（FIFO），而最小值会随着元素的出队而动态变化。例如，若最小值为队首元素，出队后最小值需要更新。为实现O(1)获取最小值，需结合队列和单调队列的特性：

1. 主队列：用普通队列（如LinkedList）存储所有元素，正常支持入队、出队操作。
2. 辅助双端队列：用一个双端队列（如ArrayDeque）维护一个非严格单调递增的序列，队首始终是当前队列的最小值。

步骤详解

1. 初始化

   • 创建两个队列：queue（主队列）和minDeque（辅助双端队列）。

2. 入队操作（push）

   • 新元素x加入queue。
   • 处理minDeque：从队尾开始，若队尾元素大于x，则不断弹出队尾（因为这些旧元素在x之后出队，不可能成为最小值），直到minDeque为空或队尾元素 ≤ x。
   • 将x加入minDeque队尾。
   • 时间复杂度：每个元素最多入队、出队minDeque一次，均摊O(1)。

3. 出队操作（pop）

   • 若queue为空，报错。
   • 弹出queue队首元素val。
   • 若val等于minDeque队首元素，说明当前最小值已出队，同步弹出minDeque队首。
   • 时间复杂度：O(1)。

4. 获取最小值（getMin）

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

5. 其他操作

   • peek（获取队首）：返回queue队首，O(1)。
   • isEmpty：检查queue是否为空，O(1)。

示例演示
操作序列：push(3)、push(1)、push(2)、getMin()、pop()、getMin()

• push(3):
  queue → [3]
  minDeque → [3]（初始直接加入）
• push(1):
  queue → [3, 1]
  minDeque队尾3 > 1，弹出3 → minDeque先为空，再加入1 → [1]
• push(2):
  queue → [3, 1, 2]
  minDeque队尾1 ≤ 2，直接加入2 → [1, 2]
• getMin() → 1（minDeque队首）
• pop()：
  弹出queue队首3，但3 ≠ minDeque队首1，故minDeque不变 → [1, 2]
• getMin() → 1

复杂度分析

• 时间复杂度：所有操作均摊O(1)。
• 空间复杂度：O(n)，最坏情况下所有元素同时存在于minDeque（如输入严格递减序列）。

关键点

• 辅助队列minDeque维护的是非严格递增序列，允许相等元素存在（如push(1)后push(1)，需保留两个1以正确处理出队）。
• 出队时仅当主队列队首等于minDeque队首才弹出，避免提前丢失最小值。

代码实现（Java）

import java.util.*;

class MinQueue {
    private Queue<Integer> queue;
    private Deque<Integer> minDeque;

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

    public void push(int x) {
        queue.offer(x);
        while (!minDeque.isEmpty() && minDeque.peekLast() > x) {
            minDeque.pollLast();
        }
        minDeque.offerLast(x);
    }

    public int pop() {
        if (queue.isEmpty()) throw new NoSuchElementException();
        int val = queue.poll();
        if (val == minDeque.peekFirst()) {
            minDeque.pollFirst();
        }
        return val;
    }

    public int getMin() {
        if (minDeque.isEmpty()) throw new NoSuchElementException();
        return minDeque.peekFirst();
    }

    public int peek() {
        if (queue.isEmpty()) throw new NoSuchElementException();
        return queue.peek();
    }

    public boolean isEmpty() {
        return queue.isEmpty();
    }
}