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

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

题目描述

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

image-20241107212305720

题意分析

给定一个整数数组和一个固定长度 k 的窗口，窗口从数组最左端开始每次右移一位，要求依次输出每个窗口内的最大值。数组长度为 $n$ 时，一共会产生 $n - k + 1$ 个结果。

关键的结构性信息藏在「每次只移动一位」里：相邻两个窗口有 $k - 1$ 个元素完全重合，只有一个元素离开、一个元素进入。如果每个窗口都独立地重新扫描一遍，那 $k - 1$ 个重合元素会被反复比较，绝大部分工作是重复劳动。数组长度可以到十万量级，$O(nk)$ 显然不可接受，这就要求把「窗口移动」处理成增量更新而非重新计算。

另一个信号是「最大值」这个查询本身很弱——我们并不需要知道窗口内元素的完整顺序，甚至不需要知道第二大是谁，只要能随时报出最大者即可。信息需求越少，能维护的状态就越精简。

边界情形：k 等于 1 时每个元素自成窗口，输出就是原数组；k 等于 $n$ 时只有一个结果；数组允许含负数和重复值，因此不能用「初值 0」这类隐含假设，重复的最大值也不能被误当成同一个元素处理。

解法：单调队列

核心思路

每个窗口重新扫描会产生 $O(nk)$ 的重复工作。窗口右移时，真正需要保留的只是仍可能成为当前或未来最大值的候选。

若旧元素在下标上更靠左，值又不大于新元素，那么只要旧元素还在窗口，新元素也一定在，并且更优；旧元素再也不可能成为最大值，可以永久删除。

用双端队列保存候选下标，并维持两个不变量：下标从队首到队尾递增，对应值严格递减；队首下标始终位于当前窗口。于是队首就是窗口最大值。

队列必须存下标而不是只存值，因为“是否过期”由位置决定。每个下标最多从队尾因被支配而删除一次，或从队首因过期而删除一次，所以即使代码有 while，总复杂度仍是线性。

解题步骤

  • 准备存下标的双端队列。
  • 遍历右端点 right，先删除队首所有不大于 right - k 的过期下标。
  • 当队尾值不大于 nums[right] 时持续弹出；这些旧候选已被当前元素支配。
  • 把 right 加入队尾，恢复值严格递减的不变量。
  • 从 right >= k - 1 开始形成完整窗口，把队首对应值加入答案。

例如 [1, 3, -1, -3, 5]、k = 3：处理 3 时会淘汰 1；处理 5 时会从队尾连续淘汰 -3、-1、3。各完整窗口的队首依次给出 3、3、5。

代码实现

import java.util.*;

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)$，证明口径是每个下标只进出一次。

易错点总结

  • 队列只存值，遇到重复最大值时无法判断哪个副本已经滑出窗口。
  • 过期条件写成 deque.first < right - k，会保留恰好刚离开窗口的下标；正确条件是“不大于”。
  • 队尾只弹一次而不用循环，可能残留多个被新元素支配的候选。
  • 从第一个元素开始输出，会把尚未达到长度 k 的区间当成完整窗口。
  • 把队尾下标与当前值直接比较，而不是比较 nums[deque.last]，会破坏单调性。
  • 看到嵌套循环就误判为 $O(n^2)$，忽略了每个元素只能被弹出一次的摊还事实。

相似题目

题目 难度 考察点
239. 滑动窗口最大值 困难 同题换编号，可直接复用同一份实现
剑指 Offer 59 - II. 队列的最大值 中等 窗口边界由入队出队决定，需封装成数据结构
862. 和至少为 K 的最短子数组 困难 在前缀和数组上维护单调递增队列，含负数
739. 每日温度 中等 单调栈求下一个更大元素，没有窗口过期约束
84. 柱状图中最大的矩形 困难 单调栈同时求左右边界，弹栈时结算答案
918. 环形子数组的最大和 中等 破环成链后用单调队列限制子数组长度