数据结构与算法 / 系统课时

双端队列

双端队列

普通 FIFO 队列约定从队尾写入、队首删除。双端队列允许在任一端插入、查看和删除。它可以实现栈或队列,也能维护滑动窗口的候选下标。

学习目标

  • 使用 Java Deque 的两端接口,理解空时的返回约定。
  • 推导窗口过期条件以及何时能淘汰较旧候选。
  • 用每个下标的入队和出队次数证明总成本。

两端接口与访问规则

操作 队首 队尾
插入 offerFirst offerLast
查看 peekFirst peekLast
删除并返回 pollFirst pollLast

查看或移除空队列时,peek、poll 系列返回 null,get、remove 对应方法抛异常。ArrayDeque 不存 null,两端操作的序列通常为摊还常数成本。动态扩容会增加单次成本,两端接口也不意味着可以安全并发修改。 Java Deque 接口 Java ArrayDeque 约定

滑动窗口怎样维护最大值

长度为 kk 的窗口移动到下标 i 时,其有效范围是 [i-k+1, i]。维护一个队列,使下标从队首到队尾递增,对应数值严格递减。队首对应当前保留的最大值。

单调双端队列维护滑动窗口最大值

  1. 从队首删除下标小于或等于 i-k 的过期项。
  2. 从队尾删除值小于或等于新值的项。新项下标更大,离开窗口更晚。在两者都有效时,旧项无法提供更大的值。相等时保留较新的候选。
  3. 将 i 加到队尾;窗口已经凑满时,输出队首对应值。

如果任务还要求并列最大值的最早下标,可将淘汰条件改为严格小于,保留较早的相等候选。存下标能直接判断是否过期。若只存数值,则需用离开窗口的值及重复次数等信息,避免把另一份相同候选误删。 Lemire 的流式窗口极值算法

Java 17 可运行示例

输入必须是非空数组,且 1 ≤ k ≤ nums.length。返回每个完整窗口的最大值。保存为 DequeSlidingWindowDemo.java,执行 javac -encoding UTF-8 --release 17 DequeSlidingWindowDemo.java,再执行 java DequeSlidingWindowDemo。

java
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)));
    }
}
text
双端队列: [10, 20, 30]
从队首移除: 10
从队尾移除: 30
剩余元素: [20]
窗口最大值: [3, 3, 5, 5, 6, 7]

每个下标入队一次,最多从某一端移除一次。虽然某轮可淘汰多个下标,但总端点操作数仍为 O(n)O(n),加上必经的外层扫描,总时间为 Θ(n)\Theta(n)。候选辅助空间是 O(k)O(k),单独返回的结果数组有 n−k+1n-k+1 个元素。 Lemire 的流式窗口极值分析

本课练习

用每个窗口的直接扫描结果复核 k=1、k=n、全相等和递减数组。再把大小比较反向,实现窗口最小值。下一章进入比较排序,先定义顺序、稳定性与性能指标。

按自己的节奏,确认真正理解。

目录与阅读设置

阅读设置

17

记录一个想法

双端队列

0 / 10000 · 笔记保存到账号。未提交的修改会在关闭、离开或刷新后丢失。

登录哪都通