LeetCode 239：滑动窗口最大值

问题定义与核心挑战

给定整数数组 nums 和窗口大小 k，需返回每个滑动窗口的最大值。例如：

• 输入：nums = [1,3,-1,-3,5,3,6,7], k=3
• 输出：[3,3,5,5,6,7]

核心挑战：

• 暴力法缺陷：直接遍历每个窗口（共 n-k+1 个），每个窗口遍历 k 个元素，时间复杂度 O(nk)，当 n=10^5 时会超时。
• 高效数据结构：需快速维护窗口内的最大值，支持新增元素和移除过期元素操作。

核心思路：单调队列（双端队列）

利用 单调递减队列 维护窗口内的元素索引，确保：

1. 队列内元素对应的值单调递减：队首始终是当前窗口的最大值。
2. 队列内仅保留当前窗口的有效元素：移除窗口左侧的过期索引。

算法步骤详解

步骤 1：初始化单调队列

使用双端队列（Deque）存储元素索引（而非值），便于判断元素是否在窗口内。

Deque<Integer> deque = new LinkedList<>();

步骤 2：遍历数组，维护单调队列

遍历每个元素 nums[i]，执行以下操作：

2.1 移除队列尾部的较小元素

当新元素 nums[i] 大于队列尾部元素对应的值时，尾部元素不可能成为当前或未来窗口的最大值（因为新元素更大且更晚离开窗口），故移除尾部元素，直到队列为空或尾部元素更大。

while (!deque.isEmpty() && nums[i] >= nums[deque.getLast()]) {
    deque.removeLast();
}
deque.addLast(i); // 将当前元素索引加入队列

2.2 移除队列头部的过期元素

窗口的左边界为 i - k + 1（当遍历到 i 时，窗口覆盖 [i-k+1, i]）。若队首元素的索引小于左边界，说明该元素已不在窗口内，需移除。

int left = i - k + 1;
while (!deque.isEmpty() && deque.getFirst() < left) {
    deque.removeFirst();
}

2.3 记录窗口最大值

当遍历到 i >= k-1（即窗口已形成）时，队首元素即为当前窗口的最大值（因队列单调递减）。

if (i >= k-1) {
    result[resultIndex++] = nums[deque.getFirst()];
}

完整代码（Java）

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

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        if (nums == null || k == 0) return new int[0];
        int n = nums.length;
        int[] result = new int[n - k + 1];
        int resultIndex = 0;
        Deque<Integer> deque = new LinkedList<>(); // 存储索引，对应值单调递减

        for (int i = 0; i < n; i++) {
            // 步骤1：移除队列尾部所有比当前元素小的索引（保持单调递减）
            while (!deque.isEmpty() && nums[i] >= nums[deque.getLast()]) {
                deque.removeLast();
            }
            deque.addLast(i); // 加入当前元素索引

            // 步骤2：移除队首的过期索引（不在当前窗口内）
            int left = i - k + 1;
            while (!deque.isEmpty() && deque.getFirst() < left) {
                deque.removeFirst();
            }

            // 步骤3：当窗口形成时，记录最大值（队首元素）
            if (i >= k - 1) {
                result[resultIndex++] = nums[deque.getFirst()];
            }
        }

        return result;
    }
}

关键逻辑解析

1. 单调队列的维护逻辑

• 尾部移除：确保队列内元素单调递减，新元素只与队尾比较，保证复杂度 O(1)（每个元素入队、出队各一次）。
• 头部移除：仅当队首元素是窗口左侧的过期元素时才移除，保证队列内始终是当前窗口的有效元素。

2. 为什么存储索引而非值？

• 需判断元素是否在窗口内（通过索引比较），而值无法提供位置信息。

3. 窗口形成的时机

• 当 i >= k-1 时，窗口 [i-k+1, i] 首次形成（如 k=3，i=2 时窗口是 [0,2]），之后每次遍历都需记录最大值。

示例验证（以示例 1 为例）

输入：nums = [1,3,-1,-3,5,3,6,7], k=3

遍历索引 i	元素 nums[i]	队列操作前	移除尾部较小元素	加入队列	移除过期元素	窗口是否形成	结果数组
0	1	[]	-	[0]	-	否	-
1	3	[0]	移除 0（1<3）	[1]	-	否	-
2	-1	[1]	-	[1,2]	-	是（i=2≥2）	[3]
3	-3	[1,2]	-	[1,2,3]	队首1≥0（3-3+1=0）	是（i=3≥2）	[3,3]
4	5	[1,2,3]	移除3（-3<5）→ 移除2（-1<5）→ 移除1（3<5）	[4]	队首4≥1（4-3+1=1）	是（i=4≥2）	[3,3,5]
5	3	[4]	-	[4,5]	队首4≥2（5-3+1=2）	是（i=5≥2）	[3,3,5,5]
6	6	[4,5]	移除5（3<6）→ 移除4（5<6）	[6]	队首6≥3（6-3+1=3）	是（i=6≥2）	[3,3,5,5,6]
7	7	[6]	移除6（6<7）	[7]	队首7≥4（7-3+1=4）	是（i=7≥2）	[3,3,5,5,6,7]

复杂度分析

• 时间复杂度：O(n)。每个元素入队、出队各一次，双端队列操作均为 O(1)。
• 空间复杂度：O(k)。队列最多存储 k 个元素（窗口大小）。

该方法通过 单调队列 高效维护窗口内的最大值，将时间复杂度从 O(nk) 降至 O(n)，是处理滑动窗口最值问题的经典方案。