Skip to content

leetcode-239-sliding-window-maximum.md

Latest commit

 

History

History
186 lines (135 loc) · 7 KB

leetcode-239-sliding-window-maximum.md

File metadata and controls

186 lines (135 loc) · 7 KB
Raw

LeetCode 239. 滑动窗口最大值 (Sliding Window Maximum)

难度：Hard　|　标签：队列、单调队列、滑动窗口　| | 单调队列模板 ⭐⭐⭐⭐

一、题目

给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。

返回滑动窗口中的 最大值。

约束

  • 1 <= nums.length <= 10^5
  • 1 <= k <= nums.length

示例

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

题目链接：https://leetcode.cn/problems/sliding-window-maximum/

二、解题思路（学习重点）

1. 暴力 O(nk) 不够

每次窗口移动后扫描 k 个数取 max，最坏 10^10 操作 → TLE。

2. 用 单调递减双端队列 维护"潜在最大值候选"

核心观察：如果窗口内 nums[i] < nums[j] 且 i < j（即 i 在 j 左侧且更小），那么 i 永远不可能成为窗口最大值（j 比它大、j 在窗口里活得也比它久）。 → 这种 i 可以直接丢掉。

维护一个 Deque<Integer>（存下标），保持队列里对应的 值严格递减：

  • 入队时：从队尾 pop 掉所有 ≤ nums[i] 的下标（它们都被新元素压制）；再把 i 加到队尾。
  • 取最大值：队首就是当前窗口最大值的下标。
  • 过期出队：若队首下标 < i - k + 1，说明它已不在窗口内，从队首 pop。

学习点 ①：单调队列 = "维护一个有用候选集合"，队首永远是当前答案。比单调栈多了一个"过期判断"。

3. 容易踩的坑

坑 处理
用 Queue<Integer> 存值 → 过期判断时无法定位是哪一个 必须存下标
入队比较时写 < 漏掉等于 → 队列里堆同值占空间 用 <= 让等值一起弹掉
过期判断用 == 应当 < i - k + 1 严格小于
用 LinkedList 慢 ArrayDeque 更快

三、详细解题步骤

步骤 1：初始化

int n = nums.length;
int[] ans = new int[n - k + 1];
Deque<Integer> dq = new ArrayDeque<>();   // 存下标，对应值严格递减

步骤 2：遍历 i = 0..n-1：

  1. 过期出队（队首）：若 dq.peekFirst() < i - k + 1 → dq.pollFirst();
  2. 入队（队尾）： 
    while (!dq.isEmpty() && nums[dq.peekLast()] <= nums[i])
    dq.pollLast();
dq.offerLast(i);
  3. 记录答案：当 i >= k - 1 时，ans[i - k + 1] = nums[dq.peekFirst()];

步骤 3：返回 ans。

关键不变量（必须能讲清）

  • 队列里对应的 nums 值 严格递减。
  • 队首始终是当前窗口最大值的下标。
  • 每个下标最多入队一次、出队一次 → 总操作 O(n)。

四、Java 题解

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        int n = nums.length;
        int[] ans = new int[n - k + 1];
        Deque<Integer> dq = new ArrayDeque<>();

        for (int i = 0; i < n; i++) {
            // 1. 过期出队
            if (!dq.isEmpty() && dq.peekFirst() < i - k + 1) {
                dq.pollFirst();
            }
            // 2. 维护单调递减：弹掉队尾比当前小的
            while (!dq.isEmpty() && nums[dq.peekLast()] <= nums[i]) {
                dq.pollLast();
            }
            // 3. 入队
            dq.offerLast(i);
            // 4. 收答案
            if (i >= k - 1) {
                ans[i - k + 1] = nums[dq.peekFirst()];
            }
        }
        return ans;
    }
}

记忆口诀：

"队尾压小留大，队首过期出窗；队首即窗口 max。"

五、复杂度

项 复杂度
时间 O(n) —— 每个下标至多入/出队各 1 次
空间 O(k) 双端队列

六、示例验证

nums = [1, 3, -1, -3, 5, 3, 6, 7], k = 3，过程（dq 显示下标）：

i nums[i] 过期 队尾压制 入队后 dq 收答案 (i≥2)
0 1 — — [0] —
1 3 — 弹 0（1≤3） [1] —
2 -1 — — [1,2] nums[1]=3
3 -3 — — [1,2,3] nums[1]=3
4 5 — 弹 3,2,1（均 ≤5） [4] nums[4]=5
5 3 — — [4,5] nums[4]=5
6 6 — 弹 5,4 [6] nums[6]=6
7 7 — 弹 6 [7] nums[7]=7

输出 [3, 3, 5, 5, 6, 7] ✅

七、复盘与延伸

一句话总结

单调递减队列：队尾压小留大，队首过期出窗，队首即为窗口最大值。

新手常见疑问（FAQ）

Q1：为什么队列里存下标而不是值？ A：需要判断“过期”（是否走出窗口）。存值无法知道是哪个位置的值，无法判过期。

Q2：队尾入队时为什么用 <= 而不是 <？ A：用 <= 可以让同值的旧元素被弹（同值的元素只保留最新一个，活得更久），节省空间。用 < 同值都保留不影响正确性，但队列会胀。

Q3：过期判断是 < i - k + 1 还是 <= i - k？ A：两者等价。窗口 [i-k+1, i]，队首下标严格小于 i-k+1 即为过期。

Q4：为什么只要 if 判过期而不是 while？ A：每次 i 只前进 1，最多只会有一个队首下标过期（其他都在 [i-k+1, i] 里）。用 if 即可。

Q5：这题用优先队列（堆）能不能做？ A：能，堆存 (值, 下标)，取顶时跳过过期元素（懒删除）。复杂度 O(n log k)，比单调队列 O(n) 差。面试可提及作为另一思路。

面试官常见 follow-up

  1. "求窗口最小值呢？" → 改成单调递增队列；队尾弹“大于等于新元素”的下标。
  2. "同时需要窗口 min 和 max（如绝对差限制）？" → 两个单调队列同时维护。即 LC 1438。
  3. "窗口大小可变（如求最短子数组和 ≥ K）？" → 前缀和 + 单调队列。即 LC 862。
  4. "跳跃游戏 VI（DP 转移带区间 max）？" → DP[i] 依赖 max(DP[i-k..i-1])，单调队列优化。即 LC 1696。
  5. "流式数据环境（元素陆续来）？" → 单调队列天然支持；每新进一个按同样三步处理即可。
  6. "二维版滑动窗口最大值（kxk 子矩阵最大）？" → 先对每行跱一次，再对结果按列跱一次。

同类型推荐（单调队列家族）