LeetCode 剑指 Offer 59 - I. 滑动窗口的最大值

约 5 分钟
文章信息 12 个分类 5 个标签
分类
LeetCode CodeTop 困难 未解决 5-10 剑指 Offer 剑指 Offer（第 2 版） 字节 阿里 快手 虾皮 商汤
标签
数组 堆（优先队列） 滑动窗口 队列 单调队列

题目描述

✅ 剑指 Offer 59 - I. 滑动窗口的最大值

image-20261001230752589

image-20260928190645307

image-20260928190645308

题意分析

给定数组和窗口长度 k，窗口从最左侧开始，每次向右移动一个位置，按顺序返回每个完整窗口内的最大值。合法窗口共有 n - k + 1 个，其中 n 为数组长度。

相邻窗口大部分元素相同，只有左侧一个元素离开、右侧一个元素加入。需要在最大值过期时快速找到接替者，不能只保留上一个窗口的最大值。数组中的重复值和负数同样参与比较；下方实现对空数组或不合法的窗口大小返回空结果。

解法：单调队列

核心思路

[!blue]

每次重新扫描窗口求最大值，最坏需要 $O(nk)$ 时间。可以只保留仍可能成为后续窗口最大值的候选，用双端队列存它们的下标：下标从头到尾递增，对应的值严格递减。

新下标 right 到来时，如果队尾旧元素的值不大于新值，就可以淘汰旧元素。理由不只是新值更大或相等，还因为它的位置更靠右，离开窗口更晚：此后只要旧元素仍在窗口里，新元素也一定在，旧元素不再可能提供更优的最大值。持续删除这样的队尾后，再加入当前下标，队列的值就恢复递减；相等时保留更新的下标。

候选还必须没有离开窗口。右端为 right 时，窗口左边界是 right - k + 1，所以下标 <= right - k 已经过期。由于队列下标递增，过期候选只可能出现在队头，可以从队头依次移除。

清理过期元素和被替代的候选后，所有仍有必要保留的值按递减顺序排列，队头就是当前最大值。较小但更靠后的候选也不能随意清空，因为前面的最大值离开后，它可能成为接替者。

前 k - 1 次加入尚未形成完整窗口，只维护队列，不输出答案。从 right = k - 1 开始，每次输出队头下标对应的数组值，顺序正好与窗口从左到右移动一致。

解题步骤

  1. 空数组、k <= 0 或 k > n 时返回空结果；否则初始化结果和空双端队列。
  2. 枚举右端 right，先移除队头中下标 <= right - k 的过期候选。
  3. 持续移除队尾中值 <= nums[right] 的候选，再将当前下标加入队尾。
  4. 若 right >= k - 1，输出 nums[队头下标]；Java 结果位置为 right - k + 1。

代码实现

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        if (nums.length == 0 || k <= 0 || k > nums.length) {
            return new int[0];
        }

        int[] ans = new int[nums.length - k + 1];
        Deque<Integer> deque = new ArrayDeque<>();

        for (int right = 0; right < nums.length; right++) {
            // 先删除已离开当前窗口的下标
            while (!deque.isEmpty() && deque.peekFirst() <= right - k) {
                deque.pollFirst();
            }

            // 更晚且不更小的新值支配旧候选，相等时保留更新位置
            while (!deque.isEmpty() && nums[deque.peekLast()] <= nums[right]) {
                deque.pollLast();
            }

            deque.offerLast(right);

            // 只有形成完整长度窗口后才输出队首最大值
            if (right >= k - 1) {
                ans[right - k + 1] = nums[deque.peekFirst()];
            }
        }

        return ans;
    }
}

func maxSlidingWindow(nums []int, k int) []int {
    if len(nums) == 0 || k <= 0 || k > len(nums) {
        return []int{}
    }

    ans := make([]int, 0, len(nums)-k+1)
    deque := make([]int, 0, k)
    for right, num := range nums {
        // 先删除已离开当前窗口的下标
        for len(deque) > 0 && deque[0] <= right-k {
            deque = deque[1:]
        }
        // 更晚且不更小的新值支配旧候选，相等时保留更新位置
        for len(deque) > 0 && nums[deque[len(deque)-1]] <= num {
            deque = deque[:len(deque)-1]
        }
        deque = append(deque, right)

        // 只有形成完整长度窗口后才输出队首最大值
        if right >= k-1 {
            ans = append(ans, nums[deque[0]])
        }
    }
    return ans
}

复杂度分析

  • 时间复杂度：$O(n)$。每个下标只入队一次，之后至多从队头或队尾删除一次，所有清理循环的总操作次数为线性数量。
  • 空间复杂度：$O(k)$ 辅助空间，队列最多保留一个窗口的下标；返回结果另需 $O(n - k + 1)$ 空间。

关键点总结

[!green]

  • 队头清理的是已过期元素，队尾清理的是已被更晚、更优元素替代的候选，两种删除原因不同。
  • 存下标才能同时判断有效期和读取数值，不能只维护一串数值。
  • 相同值优先保留新位置，使最大值能够覆盖更晚的窗口。

易错点总结

[!yellow]

  • 过期判断漏掉等号，会让刚离开窗口的元素继续参与答案，应删除 index <= right - k。
  • 队尾只清理一次，可能留下多个应被当前值替代的候选，必须使用循环。
  • 不区分队头下标和对应数组值，会把位置错误地当作最大值返回。
  • 窗口尚未达到 k 个元素就输出，会多算不完整的前缀区间。
  • 只记住当前最大值而丢掉全部较小候选，最大值过期后就无法直接得到接替者。

相似题目

题目 难度 关联与区别
862. 和至少为 K 的最短子数组 困难 同样利用单调队列淘汰不会再最优的候选，原题保存前缀和并求最短区间。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2022/44764303
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！