力扣加加 - 努力做西湖区最好的算法题解
lucifer 的博客
Github
公众号
搜索文档…
introduction
第一章 - 算法专题
第二章 - 91 天学算法
第三章 - 精选题解
第四章 - 高频考题(简单)
第五章 - 高频考题(中等)
第六章 - 高频考题(困难)
LCP 20. 快速公交
LCP 21. 追逐游戏
Number Stream to Intervals
Triple-Inversion
Kth-Pair-Distance
Minimum-Light-Radius
Largest Equivalent Set of Pairs
Ticket-Order.md
Connected-Road-to-Destination
0004. 寻找两个正序数组的中位数
0023. 合并 K 个升序链表
0025. K 个一组翻转链表
0030. 串联所有单词的子串
0032. 最长有效括号
0042. 接雨水
0052. N 皇后 II
0057. 插入区间
0065. 有效数字
0084. 柱状图中最大的矩形
0085. 最大矩形
0087. 扰乱字符串
0124. 二叉树中的最大路径和
0128. 最长连续序列
0132. 分割回文串 II
0140. 单词拆分 II
0145. 二叉树的后序遍历
0146. LRU 缓存机制
0154. 寻找旋转排序数组中的最小值 II
0212. 单词搜索 II
0239. 滑动窗口最大值
0295. 数据流的中位数
0297. 二叉树的序列化与反序列化
0301. 删除无效的括号
0312. 戳气球
330. 按要求补齐数组
0335. 路径交叉
0460. LFU 缓存
0472. 连接词
0480. 滑动窗口中位数
0483. 最小好进制
0488. 祖玛游戏
0493. 翻转对
0664. 奇怪的打印机
0679. 24 点游戏
0715. Range 模块
0726. 原子的数量
0768. 最多能完成排序的块 II
0805. 数组的均值分割
0839. 相似字符串组
0887. 鸡蛋掉落
0895. 最大频率栈
0975. 奇偶跳
0995. K 连续位的最小翻转次数
1032. 字符流
1168. 水资源分配优化
1178. 猜字谜
1203. 项目管理
1255. 得分最高的单词集合
1345. 跳跃游戏 IV
1449. 数位成本和为目标值的最大数字
1494. 并行课程 II
1521. 找到最接近目标值的函数值
1526. 形成目标数组的子数组最少增加次数
1649. 通过指令创建有序数组
1671. 得到山形数组的最少删除次数
1707. 与数组中元素的最大异或值
1713. 得到子序列的最少操作次数
1723. 完成所有工作的最短时间
1787. 使所有区间的异或结果为零
1835. 所有数对按位与结果的异或和
1871. 跳跃游戏 VII
1872. 石子游戏 VIII
1883. 准时抵达会议现场的最小跳过休息次数
1970. 你能穿过矩阵的最后一天
2009. 使数组连续的最少操作数
2025. 分割数组的最多方案数
2030. 含特定字母的最小子序列
2102. 序列顺序查询
2209. 用地毯覆盖后的最少白色砖块
2281.sum-of-total-strength-of-wizards
2306. 公司命名
5254. 卖木头块
5999. 统计数组中好三元组数目
后序
由
GitBook
提供支持
0239. 滑动窗口最大值
题目地址(239. 滑动窗口最大值)
https://leetcode-cn.com/problems/sliding-window-maximum/
题目描述
1
给定一个数组 nums,有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。
2
3
返回滑动窗口中的最大值。
4
5
6
7
进阶:
8
9
你能在线性时间复杂度内解决此题吗?
10
11
12
13
示例:
14
15
输入: nums = [1,3,-1,-3,5,3,6,7], 和 k = 3
16
输出: [3,3,5,5,6,7]
17
解释:
18
19
滑动窗口的位置 最大值
20
--------------- -----
21
[1 3 -1] -3 5 3 6 7 3
22
1 [3 -1 -3] 5 3 6 7 3
23
1 3 [-1 -3 5] 3 6 7 5
24
1 3 -1 [-3 5 3] 6 7 5
25
1 3 -1 -3 [5 3 6] 7 6
26
1 3 -1 -3 5 [3 6 7] 7
27
28
29
提示:
30
31
1 <= nums.length <= 10^5
32
-10^4 <= nums[i] <= 10^4
33
1 <= k <= nums.length
Copied!
前置知识
队列
滑动窗口
公司
阿里
腾讯
百度
字节
思路
符合直觉的想法是直接遍历 nums, 然后然后用一个变量 slideWindow 去承载 k 个元素, 然后对 slideWindow 求最大值,这是可以的,遍历一次的时间复杂度是 $N$,k 个元素求最大值时间复杂度是 $k$, 因此总的时间复杂度是 O(n * k).代码如下:
JavaScript:
1
var
maxSlidingWindow
=
function
(
nums
,
k
)
{
2
// bad 时间复杂度O(n * k)
3
if
(
nums
.
length
===
0
||
k
===
0
)
return
[];
4
let
slideWindow
=
[];
5
const
ret
=
[];
6
for
(
let
i
=
0
;
i
<
nums
.
length
-
k
+
1
;
i
++
)
{
7
for
(
let
j
=
0
;
j
<
k
;
j
++
)
{
8
slideWindow
.
push
(
nums
[
i
+
j
]);
9
}
10
ret
.
push
(
Math
.
max
(
...
slideWindow
));
11
slideWindow
=
[];
12
}
13
return
ret
;
14
};
Copied!
Python3:
1
class
Solution
:
2
def
maxSlidingWindow
(
self
,
nums
:
List
[
int
],
k
:
int
)
->
List
[
int
]:
3
if
k
==
0
:
return
[]
4
res
=
[]
5
for
r
in
range
(
k
-
1
,
len
(
nums
)):
6
res
.
append
(
max
(
nums
[
r
-
k
+
1
:
r
+
1
]))
7
return
res
Copied!
但是如果真的是这样,这道题也不会是 hard 吧?这道题有一个 follow up,要求你用线性的时间去完成。
其实,我们没必须存储窗口内的所有元素。 如果新进入的元素比前面的大,那么前面的元素就不再有利用价值,可以直接移除。这提示我们使用一个
单调递增栈
来完成。
但由于窗口每次向右移动的时候,位于窗口最左侧的元素是需要被擦除的,而栈只能在一端进行操作。
而如果你使用数组实现,就是可以在另一端操作了,但是时间复杂度仍然是 $O(k)$,和上面的暴力算法时间复杂度一样。
因此,我们考虑使用链表来实现,维护两个指针分别指向头部和尾部即可,这样做的时间复杂度是 $O(1)$,这就是双端队列。
因此思路就是用一个双端队列来保存
接下来的滑动窗口可能成为最大值的数
。
具体做法:
入队列
移除失效元素,失效元素有两种
一种是已经超出窗口范围了,比如我遍历到第 4 个元素,k = 3,那么 i = 0 的元素就不应该出现在双端队列中了 具体就是
索引大于 i - k + 1的元素都应该被清除
小于当前元素都没有利用价值了,具体就是
从后往前遍历(双端队列是一个递减队列)双端队列,如果小于当前元素就出队列
经过上面的分析,不难知道双端队列其实是一个递减的一个队列,因此队首的元素一定是最大的。用图来表示就是:
关键点解析
双端队列简化时间复杂度
滑动窗口
代码
JavaScript:
JS 的 deque 实现我这里没有写, 大家可以参考
collections/deque
1
var
maxSlidingWindow
=
function
(
nums
,
k
)
{
2
// 双端队列优化时间复杂度, 时间复杂度O(n)
3
const
deque
=
[];
// 存放在接下来的滑动窗口可能成为最大值的数
4
const
ret
=
[];
5
for
(
let
i
=
0
;
i
<
nums
.
length
;
i
++
)
{
6
// 清空失效元素
7
while
(
deque
[
0
]
<
i
-
k
+
1
)
{
8
deque
.
shift
();
9
}
10
11
while
(
nums
[
deque
[
deque
.
length
-
1
]]
<
nums
[
i
])
{
12
deque
.
pop
();
13
}
14
15
deque
.
push
(
i
);
16
17
if
(
i
>=
k
-
1
)
{
18
ret
.
push
(
nums
[
deque
[
0
]]);
19
}
20
}
21
return
ret
;
22
};
Copied!
复杂度分析
时间复杂度:$O(N * k)$,如果使用双端队列优化的话,可以到 $O(N)$
空间复杂度:$O(k)$
Python3:
1
class
Solution
:
2
def
maxSlidingWindow
(
self
,
nums
:
List
[
int
],
k
:
int
)
->
List
[
int
]:
3
q
=
collections
.
deque
()
# 本质就是单调队列
4
ans
=
[]
5
for
i
in
range
(
len
(
nums
)):
6
while
q
and
nums
[
q
[
-
1
]]
<=
nums
[
i
]:
q
.
pop
()
# 维持单调性
7
while
q
and
i
-
q
[
0
]
>=
k
:
q
.
popleft
()
# 移除失效元素
8
q
.
append
(
i
)
9
if
i
>=
k
-
1
:
ans
.
append
(
nums
[
q
[
0
]])
10
return
ans
Copied!
复杂度分析
时间复杂度:$O(N)$
空间复杂度:$O(k)$
扩展
为什么用双端队列
因为删除无效元素的时候,会清除队首的元素(索引太小了)或者队尾(元素太小了)的元素。 因此需要同时对队首和队尾进行操作,使用双端队列是一种合乎情理的做法。
大家对此有何看法,欢迎给我留言,我有时间都会一一查看回答。更多算法套路可以访问我的 LeetCode 题解仓库:
https://github.com/azl397985856/leetcode
。 目前已经 37K star 啦。 大家也可以关注我的公众号《力扣加加》带你啃下算法这块硬骨头。
以前
0212. 单词搜索 II
下一个
0295. 数据流的中位数
最近更新
1yr ago
复制链接
内容
题目地址(239. 滑动窗口最大值)
题目描述
前置知识
公司
思路
关键点解析
代码
扩展
为什么用双端队列