数据结构与算法 / 系统课时
双端队列
双端队列
普通 FIFO 队列约定从队尾写入、队首删除。双端队列允许在任一端插入、查看和删除。它可以实现栈或队列,也能维护滑动窗口的候选下标。
学习目标
- 使用 Java
Deque的两端接口,理解空时的返回约定。 - 推导窗口过期条件以及何时能淘汰较旧候选。
- 用每个下标的入队和出队次数证明总成本。
两端接口与访问规则
| 操作 | 队首 | 队尾 |
|---|---|---|
| 插入 | offerFirst |
offerLast |
| 查看 | peekFirst |
peekLast |
| 删除并返回 | pollFirst |
pollLast |
查看或移除空队列时,peek、poll 系列返回 null,get、remove 对应方法抛异常。ArrayDeque 不存 null,两端操作的序列通常为摊还常数成本。动态扩容会增加单次成本,两端接口也不意味着可以安全并发修改。 Java Deque 接口 Java ArrayDeque 约定
滑动窗口怎样维护最大值
长度为 的窗口移动到下标 i 时,其有效范围是 [i-k+1, i]。维护一个队列,使下标从队首到队尾递增,对应数值严格递减。队首对应当前保留的最大值。

- 从队首删除下标小于或等于
i-k的过期项。 - 从队尾删除值小于或等于新值的项。新项下标更大,离开窗口更晚。在两者都有效时,旧项无法提供更大的值。相等时保留较新的候选。
- 将
i加到队尾;窗口已经凑满时,输出队首对应值。
如果任务还要求并列最大值的最早下标,可将淘汰条件改为严格小于,保留较早的相等候选。存下标能直接判断是否过期。若只存数值,则需用离开窗口的值及重复次数等信息,避免把另一份相同候选误删。 Lemire 的流式窗口极值算法
Java 17 可运行示例
输入必须是非空数组,且 1 ≤ k ≤ nums.length。返回每个完整窗口的最大值。保存为 DequeSlidingWindowDemo.java,执行 javac -encoding UTF-8 --release 17 DequeSlidingWindowDemo.java,再执行 java DequeSlidingWindowDemo。
import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Deque;
public class DequeSlidingWindowDemo {
static int[] maxSlidingWindow(int[] nums, int k) {
if (nums == null || k < 1 || k > nums.length) {
throw new IllegalArgumentException("expected a non-empty array and valid k");
}
int[] result = new int[nums.length - k + 1];
Deque<Integer> candidates = new ArrayDeque<>();
for (int i = 0; i < nums.length; i++) {
while (!candidates.isEmpty() && candidates.peekFirst() <= i - k) {
candidates.pollFirst();
}
while (!candidates.isEmpty() && nums[candidates.peekLast()] <= nums[i]) {
candidates.pollLast();
}
candidates.offerLast(i);
if (i >= k - 1) {
result[i - k + 1] = nums[candidates.peekFirst()];
}
}
return result;
}
public static void main(String[] args) {
Deque<Integer> deque = new ArrayDeque<>();
deque.offerLast(20);
deque.offerFirst(10);
deque.offerLast(30);
System.out.println("双端队列: " + deque);
System.out.println("从队首移除: " + deque.pollFirst());
System.out.println("从队尾移除: " + deque.pollLast());
System.out.println("剩余元素: " + deque);
int[] nums = {1, 3, -1, -3, 5, 3, 6, 7};
System.out.println("窗口最大值: " + Arrays.toString(maxSlidingWindow(nums, 3)));
}
}双端队列: [10, 20, 30]
从队首移除: 10
从队尾移除: 30
剩余元素: [20]
窗口最大值: [3, 3, 5, 5, 6, 7]每个下标入队一次,最多从某一端移除一次。虽然某轮可淘汰多个下标,但总端点操作数仍为 ,加上必经的外层扫描,总时间为 。候选辅助空间是 ,单独返回的结果数组有 个元素。 Lemire 的流式窗口极值分析
本课练习
用每个窗口的直接扫描结果复核 k=1、k=n、全相等和递减数组。再把大小比较反向,实现窗口最小值。下一章进入比较排序,先定义顺序、稳定性与性能指标。