0239. 滑动窗口最大值
题目地址(239. 滑动窗口最大值)
题目描述
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:
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 啦。 大家也可以关注我的公众号《力扣加加》带你啃下算法这块硬骨头。 
最近更新 1yr ago