Hot 100 --- 滑动窗口最大值

本文概览：本文以LeetCode经典题目"滑动窗口最大值"为例，从暴力优化解法入手，分析其在递减数组下的最坏情况，再逐步优化到双端单调递减队列解法，系统讲解如何动态维护一个只保留可能成为最大值的候选队列，将时间复杂度从 O(nk) 优化到 O(n)

一、题目

滑动窗口最大值题目

二、题目分析

给定一个整数数组 nums 和一个滑动窗口大小 k，窗口从数组最左侧滑动到最右侧，每次滑动一位。求每次滑动后窗口中的最大值

目标：返回一个数组，包含每个窗口位置的最大值

核心问题：如何在窗口滑动时高效地维护最大值，而不是每次都重新扫描整个窗口

思路概览

Java实现代码如下

public int[] maxSlidingWindow(int[] nums, int k) {
    int[] res = new int[nums.length - k + 1];

    if (nums.length == 0 || k == 0 || k > nums.length || k < 0)
        return res;

    // 窗口队列，记录窗口内可能最大的值的下标，且是单调递减的
    Deque<Integer> deque = new ArrayDeque<>();

    for (int i = 0; i < nums.length; i++) {
        // 删除队首过期元素
        while (!deque.isEmpty() && deque.peekFirst() < i - k + 1) {
            deque.pollFirst();
        }
        // 删除队尾比即将添加的元素小的元素
        while (!deque.isEmpty() && nums[deque.peekLast()] < nums[i]) {
            deque.pollLast();
        }
        // 添加元素下标（队尾添加）
        deque.offerLast(i);
        // 当窗口形成后，添加元素到结果数组中
        if (i >= k - 1) {
            res[i - k + 1] = nums[deque.peekFirst()];
        }
    }
    return res;
}

思路简要说明

单调递减队列：用一个双端队列维护窗口内可能成为最大值的元素下标，队列中下标对应的值单调递减
队首就是最大值：由于队列单调递减，队首下标对应的值就是当前窗口的最大值
动态维护：每次窗口滑动，先从队首删除过期元素（已不在窗口内的），再从队尾删除比新元素小的元素（它们不可能成为后续窗口的最大值），最后将新元素下标加入队尾

三、思路详解

暴力优化解法（会超时）

最自然的想法是：对每个窗口都遍历一遍找最大值，时间复杂度 O(nk)

一个直观的优化是：窗口滑动时，如果移出去的元素不是上一个窗口的最大值，那当前窗口的最大值就是 上一个最大值 和 新加入元素 中的较大值，不需要重新扫描整个窗口

public int[] maxSlidingWindow(int[] nums, int k) {
    int[] res = new int[nums.length - k + 1];

    if (nums.length == 0 || k == 0 || k > nums.length || k < 0)
        return res;

    int max = nums[0];

    // 初始化窗口
    for (int i = 0; i < k; i++) {
        max = Math.max(max, nums[i]);
    }
    res[0] = max;

    // 移动窗口，只比较新加入的元素和上一个窗口的最大值
    for (int i = k; i < nums.length; i++) {
        // 如果移除的元素是最大值，需要重新计算当前窗口的最大值
        if (nums[i - k] == max) {
            max = nums[i - k + 1];
            for (int j = i - k + 2; j <= i; j++) {
                max = Math.max(max, nums[j]);
            }
        }
        // 不是则直接更新最大值
        max = Math.max(max, nums[i]);
        res[i - k + 1] = max;
    }
    return res;
}

这个方案在大多数情况下表现不错，但有一个致命的极端情况：递减数组

例如 nums = [9, 8, 7, 6, 5, 4, 3, 2, 1], k = 3

窗口 [9, 8, 7]，最大值 9
窗口滑动到 [8, 7, 6]，移出去的 9 恰好是最大值，必须重新扫描整个窗口找最大值，结果是 8
窗口滑动到 [7, 6, 5]，移出去的 8 又是最大值，又要重新扫描...

在递减数组中，每次窗口滑动都会移出当前最大值，导致每次都要重新扫描 k 个元素，时间复杂度退化为 O(nk)，直接超时

时间复杂度：最好 O(n)，最坏 O(nk)
核心瓶颈：当移出的元素恰好是最大值时，无法快速知道"次大值"是谁，只能重新扫描
关键思考：能否维护一个结构，让我们始终知道当前窗口的最大值和可能的候选最大值？

双端单调递减队列解法

思路分析

暴力优化解法的问题在于：当最大值被移出窗口时，我们不知道次大值是谁，只能重新扫描

那如果我们提前把不可能成为最大值的元素排除掉，只保留那些"有资格"成为最大值的候选呢？

举例：第一个窗口 [5, 3, 4]，其中 3 不需要保留，因为在 3 出去窗口之前 4 都不会出去，说明 3 永远不可能成为新的窗口最大值——只要 4 还在，最大值就轮不到 3。所以应该把 3 移除，队列中只保留 [5, 4]

这就是单调递减队列的核心思想：队列中只保留可能成为窗口最大值的元素，且保持单调递减，这样队首永远是当前窗口的最大值

队列中存储的是下标而非值

因为我们需要根据位置来判断元素是否已经滑出窗口。存储下标可以同时知道元素的值（通过 nums[下标]）和元素的位置（下标本身），方便进行过期判断

三个操作

每次窗口滑动，队列需要进行三个操作：

删除队首过期元素：如果队首下标已经不在当前窗口范围内（deque.peekFirst() < i - k + 1），就从队首移除，确保队列中都是当前窗口内的元素
删除队尾比新元素小的元素：如果队尾下标对应的值小于新加入的元素，说明队尾那些元素永远不可能成为后续窗口的最大值了（新元素比它们大，且比它们晚出窗口），所以从队尾依次移除，直到队列为空或队尾元素不小于新元素
添加新元素下标：将新元素的下标从队尾加入

为什么从队尾删除是安全的？

因为队列是单调递减的，新元素比队尾元素大，意味着队尾元素既比新元素小，又比新元素先出窗口，所以队尾元素在后续任何窗口中都不可能成为最大值，可以放心删除

举例说明

以 nums = [1, 3, -1, -3, 5, 3, 6, 7], k = 3 为例

步骤	i	nums[i]	操作	队列（下标）	队列（值）	窗口	最大值
1	0	1	加入0	[0]	[1]	[1]	-
2	1	3	0<3，删0；加入1	[1]	[3]	[1,3]	-
3	2	-1	加入2	[1,2]	[3,-1]	[1,3,-1]	3
4	3	-3	加入3	[1,2,3]	[3,-1,-3]	[3,-1,-3]	3
5	4	5	1过期删；-3<5删3；-1<5删2；加入4	[4]	[5]	[-1,-3,5]	5
6	5	3	加入5	[4,5]	[5,3]	[-3,5,3]	5
7	6	6	3<6删5；5<6删4；加入6	[6]	[6]	[5,3,6]	6
8	7	7	6<7删6；加入7	[7]	[7]	[3,6,7]	7

最终结果为 [3, 3, 5, 5, 6, 7]

时间复杂度：O(n)，每个元素最多入队一次、出队一次
空间复杂度：O(k)，队列中最多存储 k 个下标