239. 滑动窗口最大值

题目链接（困难）

题目描述

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

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

数据范围：

1 <= nums.length <= 10^5
-10^4 <= nums[i] <= 10^4
1 <= k <= nums.length

示例

示例 1：

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

滑动窗口的位置                最大值
---------------               -----
[1  3  -1] -3  5  3  6  7       3
 1 [3  -1  -3] 5  3  6  7       3
 1  3 [-1  -3  5] 3  6  7       5
 1  3  -1 [-3  5  3] 6  7       5
 1  3  -1  -3 [5  3  6] 7       6
 1  3  -1  -3  5 [3  6  7]      7

示例 2：

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

核心思路

朴素做法：对每个窗口遍历 k 个元素求最大值，时间 $O(nk)$，会超时。

优化方向：相邻窗口共享 k-1 个元素，只有 1 个元素变化，可以利用这个特点避免重复计算。

三种解法：

优先队列（大根堆）：把窗口内的元素放入大根堆，堆顶就是最大值；
单调队列（推荐）：用双端队列维护一个单调递减的下标序列，队首就是窗口最大值；
分块 + 前后缀最大值：预处理每个分块的前缀最大值和后缀最大值，$O(1)$ 得到每个窗口的最大值。

方法一：优先队列（大根堆）

思路及解法

用大根堆维护窗口内的所有元素，堆顶就是最大值。

关键问题：堆顶元素可能已经滑出窗口了。

解决方法：堆里存 (值, 下标)，每次取堆顶时，若下标超出窗口左边界，则弹出，直到堆顶下标在窗口内。

流程：

把前 k 个元素放入堆中；
记录堆顶作为第一个窗口的最大值；
每滑动一步：把新元素入堆，然后不断弹出堆顶直到堆顶下标在窗口内，记录新的堆顶。

Python 的 heapq 是小根堆，所以入堆时存 (-nums[i], i)，用小根堆模拟大根堆。

代码

import heapq

class Solution:
    def maxSlidingWindow(self, nums: list[int], k: int) -> list[int]:
        n = len(nums)
        # Python 默认是小根堆，存 -nums[i] 模拟大根堆
        q = [(-nums[i], i) for i in range(k)]
        heapq.heapify(q)

        ans = [-q[0][0]]
        for i in range(k, n):
            heapq.heappush(q, (-nums[i], i))
            # 弹出已经滑出窗口的堆顶
            while q[0][1] <= i - k:
                heapq.heappop(q)
            ans.append(-q[0][0])

        return ans

复杂度分析

时间复杂度：$O(n \log n)$，每个元素最多入堆、出堆一次，堆操作 $O(\log n)$。
空间复杂度：$O(n)$，堆最多存 n 个元素。

方法二：单调队列（推荐）✅

思路及解法

关键观察：窗口内若有两个下标 i < j，且 nums[i] <= nums[j]，那么当窗口右移时：

只要 j 还在窗口中，i 一定也还在；
nums[j] 的存在使得 nums[i] 永远不会成为窗口最大值。

结论：nums[i] 可以永久移除。

因此，可以用一个双端队列维护窗口内的下标，满足：

下标从小到大排列；
对应的 nums 值严格递减。

操作：

入队时：不断弹出队尾中比当前元素小的（因为当前元素更大，它们永远不会成为最大值）；
出队时：若队首下标超出窗口左边界，弹出。

队首就是当前窗口的最大值。

为什么队列内的值是严格递减的：若相邻两个下标对应的值相等或递增，那么靠左的会被靠右的「压制」，早就被弹掉了。

代码

class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        dq = deque()  # 存下标，对应值单调递减
        res = []
        
        for i, num in enumerate(nums):
            # 1. 队尾弹出所有比当前 num 小的元素
            while dq and nums[dq[-1]] <= num:
                dq.pop()
            
            # 2. 当前下标入队
            dq.append(i)
            
            # 3. 队首滑出窗口则弹出
            if dq[0] <= i - k:
                dq.popleft()
            
            # 4. 窗口形成后记录最大值
            if i >= k - 1:
                res.append(nums[dq[0]])
        
        return res

复杂度分析

时间复杂度：$O(n)$，每个下标最多入队、出队一次。
空间复杂度：$O(k)$，队列中最多存 k 个下标。

方法三：分块 + 前后缀最大值

思路及解法

把数组按 k 个一组分成若干块（最后一组可能不足 k 个）。

对于窗口 [i, i+k-1]：

若 i 是 k 的倍数，窗口恰好是一个分组，最大值就是分组最大值；
否则，窗口会横跨两个分组，含有第一个分组的后缀和第二个分组的前缀。

预处理：

prefix_max[i]：以 i 结尾的当前分组的前缀最大值；
suffix_max[i]：以 i 开始的当前分组的后缀最大值。

递推式：

$\text{prefix\_max}[i] = \begin{cases} nums[i], & i \bmod k = 0 \\ \max(\text{prefix\_max}[i-1],\ nums[i]), & \text{其他} \end{cases}$ $\text{suffix\_max}[i] = \begin{cases} nums[i], & i = n-1 \ \text{或}\ (i+1) \bmod k = 0 \\ \max(\text{suffix\_max}[i+1],\ nums[i]), & \text{其他} \end{cases}$

每个窗口的答案：

$\max(\text{suffix\_max}[i],\ \text{prefix\_max}[i + k - 1])$

代码

class Solution:
    def maxSlidingWindow(self, nums: list[int], k: int) -> list[int]:
        n = len(nums)
        prefix_max = [0] * n
        suffix_max = [0] * n

        # 前缀最大值
        for i in range(n):
            if i % k == 0:
                prefix_max[i] = nums[i]
            else:
                prefix_max[i] = max(prefix_max[i - 1], nums[i])

        # 后缀最大值
        for i in range(n - 1, -1, -1):
            if i == n - 1 or (i + 1) % k == 0:
                suffix_max[i] = nums[i]
            else:
                suffix_max[i] = max(suffix_max[i + 1], nums[i])

        ans = []
        for i in range(n - k + 1):
            ans.append(max(suffix_max[i], prefix_max[i + k - 1]))
        return ans

复杂度分析

时间复杂度：$O(n)$，三次线性扫描。
空间复杂度：$O(n)$，两个数组。

三种方法对比

方法	时间	空间	特点
优先队列	$O(n \log n)$	$O(n)$	思路直观，但效率不如单调队列
单调队列	$O(n)$	$O(k)$	最优解，面试首选
分块前后缀	$O(n)$	$O(n)$	思路巧妙，类似稀疏表

关键细节

1. 单调队列的核心思想

「一个元素如果比它右边的小，那么它永远不会成为最大值」。

具体地说：若在窗口内 i < j，nums[i] <= nums[j]，那么只要 j 还在窗口中，i 就不可能是最大值。因为：

窗口右移时，i 会比 j 更早离开窗口；
只要 i 在窗口内，j 一定也在；
nums[j] >= nums[i]，所以最大值不会是 nums[i]。

2. 队列中存储下标而不是值

存下标有两个好处：

可以检查是否滑出窗口（比较下标与 i - k）；
可以通过 nums[q[-1]] 访问对应的值。

3. 入队时的 `>=` 和 `>`

while q and nums[i] >= nums[q[-1]]:
    q.pop()

用 >= 表示相等时也弹出，保持队列严格递减。用 > 也可以，但队列中会有相等的元素，处理起来稍麻烦。推荐用 >=。

4. 什么时候记录答案

在 i >= k - 1 之后才形成第一个完整窗口，从这里开始记录。

5. 优先队列为什么是 $O(n \log n)$

最坏情况下（如数组严格递增），每次新元素都比前面大，前面的元素永远不会被弹出，堆里最多存 n 个元素。每次堆操作 $O(\log n)$，共 $n$ 次。

6. 分块法的直观理解

把数组按 k 分组后：

每个窗口要么恰好覆盖一个完整分组；
要么横跨两个相邻分组，取「左组后缀」和「右组前缀」的最大值。

这是「预处理 + 查询」的思路，和稀疏表（Sparse Table）类似。

7. 与「滑动窗口」其他题的联系

本题：窗口最大值（单调队列）；
LC 76：最小覆盖子串（双指针）；
LC 438：找到所有字母异位词（固定长度窗口 + 计数）；
LC 3：无重复字符的最长子串（双指针）。

单调队列适合「求窗口极值」类问题。

总结

核心问题：求每个长度为 k 的滑动窗口中的最大值；
优先队列：
- 存 (-值, 下标)，小根堆模拟大根堆；
- 堆顶滑出窗口时弹出；
- 时间 $O(n \log n)$、空间 $O(n)$；
单调队列（推荐）：
- 双端队列维护下标，保持 nums 值严格递减；
- 入队时弹出所有比当前元素小的队尾；
- 出队时弹出滑出窗口的队首；
- 队首即当前窗口最大值；
- 时间 $O(n)$、空间 $O(k)$；
分块前后缀：
- 预处理每个分块的前缀最大值和后缀最大值；
- 每个窗口答案 = max(suffix_max[i], prefix_max[i+k-1])；
- 时间 $O(n)$、空间 $O(n)$；
通用套路：「滑动窗口极值」→ 单调队列。

239. 滑动窗口最大值

239. 滑动窗口最大值

题目描述

示例

核心思路

方法一：优先队列（大根堆）

思路及解法

代码

复杂度分析

方法二：单调队列（推荐）✅

思路及解法

代码

复杂度分析

方法三：分块 + 前后缀最大值

思路及解法

代码

复杂度分析

三种方法对比

关键细节

1. 单调队列的核心思想

2. 队列中存储下标而不是值

3. 入队时的 >= 和 >

4. 什么时候记录答案

5. 优先队列为什么是 $O(n \log n)$

6. 分块法的直观理解

7. 与「滑动窗口」其他题的联系

总结

相关题目

3. 入队时的 `>=` 和 `>`