239. 滑动窗口最大值
题目描述
给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。
你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。
返回 滑动窗口中的最大值。
示例 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]提示
1 <= nums.length <= 10^5-10^4 <= nums[i] <= 10^41 <= k <= nums.length
题解笔记：暴力、大顶堆、单调队列
一、先理解题目本质
这道题的核心是：
- 窗口大小固定为
k - 窗口不断向右滑动
- 每次都要快速得到当前窗口的最大值
最直接的想法是：
每形成一个窗口，就把窗口里的元素都扫一遍，找最大值。
这就是暴力解法。
但如果数组很长，每次都重新扫，会有很多重复计算，所以就会继续优化到：
- 大顶堆
- 单调队列
解法一：暴力解法
思路
每次窗口形成后，直接遍历这个窗口里的所有元素，找到最大值。
例如窗口是：
[3, -1, -3]那就把这 3 个数重新比较一遍，得到最大值 3。
代码
from typing import List
class Solution:
def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
ans = []
for left in range(len(nums) - k + 1):
max_num = nums[left]
for right in range(left, left + k):
max_num = max(max_num, nums[right])
ans.append(max_num)
return ans复杂度
- 时间复杂度：
O(n * k) - 空间复杂度：
O(1)（不算返回结果）
优缺点
优点
- 最容易理解
- 非常适合刚开始学这题时打基础
缺点
- 每个窗口都重新扫描一遍
- 重复计算很多
- 数据大时容易超时
解法二：大顶堆
先说结论
大顶堆可以做，而且比暴力解法更高效。
不过它不是最优解，通常复杂度是：
- 时间复杂度：
O(n log n)（严格说更稳妥） - 空间复杂度：
O(n)
1. 为什么会想到堆
因为这题每次都在问：
当前窗口里的最大值是谁？
而堆最擅长做的事就是：
- 插入一个数
- 快速拿到最大值（或最小值）
所以一个很自然的想法就是：
- 把窗口相关元素放进堆里
- 每次从堆顶拿最大值
2. 但为什么不能直接只存值
问题在于：
窗口会向右移动，旧元素会离开窗口。
例如：
[3, -1, -3]下一步变成：
[-1, -3, 5]这里的 3 已经离开窗口了。
但如果它还在堆里，并且还在堆顶，那就会影响答案。
所以只存值不够，还必须存：
- 值
- 下标
3. 为什么 Python 里要存 (-值, 下标)
因为 Python 的 heapq 默认是小顶堆，没有原生大顶堆。
所以我们常用一个技巧：
- 把值取负
- 原本最大的值，负数后反而最小
- 这样小顶堆就能模拟大顶堆
例如数字 5，下标为 4，会存成：
(-5, 4)其中：
-5：用来模拟大顶堆4：表示它原来的下标
4. 什么叫“过期元素”
假设当前窗口范围是：
[left, right]如果某个元素的下标：
idx < left就说明它已经滑出窗口，不能再参与当前窗口最大值比较了。
这类元素就叫：
过期元素
5. 什么叫“懒删除”
堆不擅长删除中间任意位置的元素。
所以我们不主动去堆里搜索并删除所有过期元素，而是：
- 只要堆顶过期，就把堆顶弹出
- 一直弹到堆顶合法为止
这就叫：
懒删除
代码里通常是：
while heap[0][1] < left:
heapq.heappop(heap)代码
from typing import List
import heapq
class Solution:
def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
heap = []
ans = []
for i, num in enumerate(nums):
# 入堆：(-值, 下标)
heapq.heappush(heap, (-num, i))
# 窗口形成后再开始记录答案
if i >= k - 1:
left = i - k + 1
# 懒删除：弹掉所有过期堆顶
while heap[0][1] < left:
heapq.heappop(heap)
# 堆顶就是当前窗口最大值
ans.append(-heap[0][0])
return ans复杂度
- 时间复杂度：
O(n log n) - 空间复杂度：
O(n)
优缺点
优点
- 思路比单调队列更直观
- 很适合从暴力解法继续进阶
- 也能解决这道题
缺点
- 不是最优解
- 代码里要理解“过期元素”和“懒删除”
- 堆中可能保留一些已经过期但暂时不在堆顶的元素
解法三：单调队列
先说结论
这是这道题的最优解。
- 时间复杂度：
O(n) - 空间复杂度：
O(k)
1. 核心思想
我们希望队列里维护的是：
可能成为当前窗口最大值的元素下标
并且让这些下标对应的值，保持单调递减。
也就是说：
- 队首最大
- 队尾最小
这样每次窗口形成后：
- 队首就是当前窗口最大值的下标
- 直接取
nums[deque[0]]就行
2. 为什么要存下标，不直接存值
因为窗口会移动，我们需要判断队首元素是否已经离开窗口。
如果只存值，就不知道它对应的是哪个位置。
所以单调队列里存的是：
下标3. 队列维护规则
遍历到 i 时，做三件事。
第一步：移除队首过期元素
如果队首下标已经不在窗口内：
deque[0] < i - k + 1就把它弹掉。
第二步：保持单调递减
如果当前元素 nums[i] 比队尾对应的值还大，那么队尾那个元素以后就不可能成为最大值了。
因为：
- 它比当前元素小
- 它还比当前元素更早过期
所以直接弹出队尾，直到队列重新单调递减。
第三步：把当前下标加入队尾
这样队列中保留的，都是未来仍有机会成为最大值的元素。
代码
from typing import List
from collections import deque
class Solution:
def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
q = deque()
ans = []
for i, num in enumerate(nums):
# 1. 删除窗口左边已经过期的下标
while q and q[0] < i - k + 1:
q.popleft()
# 2. 维护单调递减队列
while q and nums[q[-1]] < num:
q.pop()
# 3. 当前下标加入队尾
q.append(i)
# 4. 窗口形成后，队首就是最大值
if i >= k - 1:
ans.append(nums[q[0]])
return ans复杂度
- 时间复杂度：
O(n) - 空间复杂度：
O(k)
为什么是 O(n)
因为每个元素最多只会：
- 进队一次
- 出队一次
不会反复进出，所以总操作次数和 n 成正比。
优缺点
优点
- 最优解
- 性能最好
- 是这道题的经典标准答案
缺点
- 对初学者来说抽象一点
- 第一次接触“单调队列”时不如堆直观
评论 (0)