type
status
date
summary
tags
category
icon
password
featured
freq
difficulty
给你一个整数数组
nums,有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的
k 个数字。滑动窗口每次只向右移动一位。返回 滑动窗口中的最大值 。
示例 1:
示例 2:
解法一:最大堆
我们想要随时拿到当前窗口的最大值,可以使用最大堆的“堆顶即最大”的特性。
窗口在滑动,旧元素可能已经滑出窗口,所以需要能懒删除那些“已过期”的堆顶:过期的元素不急着删,等它蹦到堆顶再丢。
- 堆里放二元组
(-nums[i], i)(用负号模拟大根堆),既能按值取最大,也能用索引判断是否过期。
- 每次右移窗口:把新元素入堆,然后不停弹出堆顶,直到堆顶索引仍在当前窗口范围内;此时堆顶就是当前窗口最大值。
复杂度
- 时间:
O(n log n)(每个元素入堆一次,最坏弹出也近一次)
- 空间:
O(n)(堆最坏可堆满)
解法二:单调队列(最优解)
相邻窗口共享 k-1 个元素,只有一个新进的元素替代滑出的。
既然越新的、越大的值更有希望当最大,那凡是更旧且更小的元素,可以在进新元素时“当场淘汰”。
这就把“求最大值”变成了维护一个值单调递减的双端队列。
具体步骤:
- 队列中存元素的索引,对应的
nums[idx]严格单调递减。
- 进新元素
j时:不断弹出队尾所有比nums[j]小(或等于也可弹)的索引,再把j追加到队尾。
- 窗口右移后,如队首索引已不在窗口内(
<= i-k),就从队首弹出。
- 队首索引对应的值就是窗口最大值——因为队列保持了“从大到小”的候选序。
复杂度
- 时间:
O(n)(每个索引最多入队一次、出队一次)
- 空间:
O(k)(队列里最多存一个窗口内的若干索引)
解法三:分块预处理
一次线性预处理,让每个长度为
k 的窗口都能在 O(1) 时间查询。把数组按
k 分块:一个窗口要么完全落在某块,要么是前一块的后缀 + 下一块的前缀。- 定义两张表:
prefixMax[i]:在本块内(从块头开始)到位置i的前缀最大;suffixMax[i]:在本块内,从位置i到块尾的后缀最大。
- 对任意窗口
[i, i+k-1]: - 若跨块:答案是
max(suffixMax[i], prefixMax[i+k-1]); - 若正好块对齐:等价于上式(两者都等于整块最大)。
复杂度
- 时间:
O(n)(两次线性扫描 + 一次组装)
- 空间:
O(n)(两张辅助表)
- 作者:Fan Luo
- 链接:https://fanluo.me/article/leetcode-239-滑动窗口最大值
- 声明:本文采用 CC BY-NC-SA 4.0 许可协议,转载请注明出处。
上一篇
[Leetcode 236] 二叉树的最近公共祖先
下一篇
[Leetcode 240] 搜索二维矩阵 II
