LeetCode 239. 滑动窗口最大值

2026-09-21 HGNULB 约 5 分钟

文章信息 28 个分类 5 个标签

分类

LeetCode CodeTop 困难已解决需加强 100-200 LeetCode 热题 100 腾讯字节阿里华为微软美团拼多多京东小米百度网易小红书快手滴滴携程 B站虾皮商汤旷视猿辅导图森

题目描述

✅ 239. 滑动窗口最大值

题意分析

给定整数数组 nums，一个长度固定为 k 的连续窗口从左向右移动，每次移动一个位置。按窗口出现的顺序返回各自的最大值，共有 n - k + 1 个结果，其中 n 为数组长度。

相邻窗口共享 k - 1 个元素，变化只有最左侧元素离开、右侧新元素进入。难点是原来的最大值离开后，如何快速知道剩余元素中的最大值。题目保证 1 <= k <= n；重复值和负数也必须正常处理。

解法：单调队列维护候选下标

核心思路

[!blue]

如果每移动一次都遍历整个窗口，最坏需要 $O(nk)$ 时间。只记住当前最大值也不够：它一旦离开窗口，就不知道谁来接替。因此要保留一些仍有机会成为最大值的候选。

用双端队列保存候选的下标。下标从队头到队尾递增，对应的值严格递减：队头是最大的候选，后面保留的是它离开后可能接替的元素。存下标既能取得数值，也能判断这个元素是否还在窗口内。

新下标 i 到来时，设队尾旧下标为 j。若 nums[j] <= nums[i]，旧候选就可以删除：新元素的值不小于它，而且位置更靠右、离开窗口更晚。此后只要旧元素还在窗口内，新元素也一定在，旧元素不可能提供更好的最大值。反复删除这样的队尾，再放入 i，就恢复了值的递减顺序；相等时也保留更新的下标。

还要清理已离开窗口的候选。右端点为 i 时，当前窗口左边界是 i - k + 1，下标 <= i - k 的元素已经过期。因为下标递增，过期候选只可能出现在队头，从队头依次删除即可。

清理后，队列只保留当前范围内未被更优元素替代的候选，最大的值就在队头。前 k - 1 次遍历还没有形成完整窗口；从 i = k - 1 开始，每次记录队头对应的值。

解题步骤

创建空双端队列和结果数组，依次遍历右端点 i。

只要队头下标 <= i - k，就将其删除，确保留下的候选未过期。

只要队尾对应的值 <= nums[i]，就删除队尾；随后将 i 加到队尾。

当 i >= k - 1 时，将 nums[队头下标] 写入当前窗口的结果。Java 中对应的结果下标是 i - k + 1。

代码实现

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

        for (int i = 0; i < nums.length; i++) {
            // 当前窗口左边界是 i 减 k 加一，更早的下标已过期。
            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 {
    result := make([]int, 0, len(nums)-k+1)
    deque := make([]int, 0, k)

    for i := range nums {
        // 当前窗口左边界是 i 减 k 加一，更早的下标已过期。
        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)$，不计返回结果。队列最多保存当前窗口的 k 个下标；返回结果另占 $O(n-k+1)$ 空间。

关键点总结

[!green]

队头删除的是已经过期的元素，队尾删除的是已被新元素替代的候选，两种删除理由不同。

下标递增保证能从队头清理过期元素，值递减保证能从队头读取最大值。

当前较小的候选不能全部丢弃；只要它没有被更靠右且不小于它的元素替代，最大值离开后它仍可能有用。

易错点总结

[!yellow]

过期条件是 index <= i - k，等价于 index < i - k + 1；漏掉等号会保留刚离开窗口的元素。

清理队尾必须使用循环，新元素可能同时替代多个候选；按本实现的比较条件，应清理旧队尾后再放入当前下标。

必须在 i >= k - 1 后才输出，未填满的窗口不属于答案。

队列保存的是下标，输出时需要读取对应的 nums 值。

相似题目

题目	难度	关联与区别
862. 和至少为 K 的最短子数组	困难	同样利用单调队列淘汰不会再最优的候选，原题保存前缀和并求最短区间。
补充题 212. 滑动窗口最大值	困难	都用单调队列维护窗口最大值；补充题还规定非法窗口大小时返回空数组。
1438. 绝对差不超过限制的最长连续子数组	中等	用单调队列删除过期且不可能更优的候选；本题按值维护窗口最大值，该题同时维护窗口最大值和最小值。

.article-image.is-loading { width: var(--article-image-width, 100%); height: auto; } .article-image.is-loading img { position: static; width: auto !important; height: auto !important; opacity: 1; pointer-events: auto; } .article-image-spinner { display: none; }

转载与许可

作者 HGNULB

链接 https://hgnulb.github.io/blog/2026/01328393

许可本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！