LeetCode 补充题 212. 滑动窗口最大值

约 4 分钟
文章信息 2 个分类 5 个标签
分类
补充题 困难
标签
数组 堆（优先队列） 滑动窗口 队列 单调队列

题目描述

:::fold-green 相关原题

LeetCode 原题： ✅ 239. 滑动窗口最大值

力扣保证窗口长度合法；本文额外约定空数组或非法窗口长度返回空数组。

:::

给定整数数组 nums 和窗口长度 k，按窗口从左到右的顺序返回各窗口最大值。

若 k <= 0、数组为空或 k 超过数组长度，返回空数组。

示例 1：

输入： nums = [1,2], k = 3
输出： []

提示：

  • 元素为 32 位整数。
  • 合法窗口每次向右移动一位。

题意分析

相邻窗口只增加一个元素、删除一个元素，重新扫描整个窗口会重复工作。保存仍可能成为最大值的下标，让过期判断和候选淘汰都能在队列两端完成。

解法：边界检查 + 单调队列

核心思路

[!blue]

队列保存下标，对应值从队首到队尾递减。队首既在当前窗口中，又不小于其后的候选，所以它就是最大值。

处理下标 i 时，先从队首删除 <= i-k 的过期下标。然后从队尾删除不大于新值的旧下标：新值至少一样大，且出现更晚、过期更晚，旧候选之后不可能更优。再把 i 入队。

只有凑满 k 个元素才写答案。窗口参数检查必须放在结果数组分配和队列访问之前，避免非法 k 导致负长度或空队列访问。

解题步骤

  1. 检查 k，非法窗口或空数组直接返回空结果。
  2. 对当前下标 i，删除队首不在窗口内的下标。
  3. 删除队尾值不大于 nums[i] 的候选，再将 i 入队。
  4. 当 i>=k-1 时，输出队首下标对应的值。

代码实现

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

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

        for (int i = 0; i < nums.length; i++) {
            while (!deque.isEmpty() && deque.peekFirst() <= i - k) {
                deque.pollFirst();
            }

            while (!deque.isEmpty() && nums[deque.peekLast()] <= nums[i]) {
                deque.pollLast();
            }

            deque.offerLast(i);

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

        return result;
    }
}

func maxSlidingWindow(nums []int, k int) []int {
    if k <= 0 || k > len(nums) {
        return []int{}
    }
    result := make([]int, 0, len(nums)-k+1)
    deque := make([]int, 0, k)

    for i := range nums {
        for len(deque) > 0 && deque[0] <= i-k {
            deque = deque[1:]
        }
        for len(deque) > 0 && nums[deque[len(deque)-1]] <= nums[i] {
            deque = deque[:len(deque)-1]
        }
        deque = append(deque, i)
        if i >= k-1 {
            result = append(result, nums[deque[0]])
        }
    }
    return result
}

复杂度分析

  • 时间复杂度：$O(n)$。每个下标入队一次，并至多从队首或队尾移除一次，嵌套循环的总操作数仍为线性。
  • 空间复杂度：辅助队列 $O(k)$，不计输出。

关键点总结

[!green]

先在分配结果空间前验证窗口长度，再用单调递减的下标队列维护候选，队首即当前最大值。

易错点总结

[!yellow]

  • 队列保存下标，才能判断候选是否已经离开窗口。
  • 当前窗口左端为 i-k+1，所以下标不大于 i-k 时就已过期。
  • 相等值可以删除较早下标，因为新下标过期更晚。
  • 满 k 个元素后才输出，且参数检查必须早于结果数组分配。

相似题目

题目 难度 关联与区别
239. 滑动窗口最大值 困难 单调队列维护窗口最大值的过程相同；该题保证窗口长度合法，本题还约定空数组或非法窗口长度返回空结果。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2026/294865232084
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！