0239. 滑动窗口最大值 #
- 标签:队列,数组、滑动窗口、单调队列、堆(优先队列)
- 难度:困难
题目大意 #
描述:给定一个整数数组 nums
,再给定一个整数 k
,表示为大小为 k
的滑动窗口从数组的最左侧移动到数组的最右侧。我们只能看到滑动窗口内的 k
个数字,滑动窗口每次只能向右移动一位。
要求:返回滑动窗口中的最大值。
说明:
- $1 \le nums.length \le 10^5$。
- $-10^4 \le nums[i] \le 10^4$。
- $1 \le k \le nums.length$。
示例:
- 示例 1:
|
|
- 示例 2:
|
|
解题思路 #
暴力求解的话,需要使用二重循环遍历,其时间复杂度为 $O(n * k)$。根据题目给定的数据范围,肯定会超时。
我们可以使用优先队列来做。
思路 1:优先队列 #
- 初始的时候将前
k
个元素加入优先队列的二叉堆中。存入优先队列的是数组值与索引构成的元组。优先队列将数组值作为优先级。 - 然后滑动窗口从第
k
个元素开始遍历,将当前数组值和索引的元组插入到二叉堆中。 - 当二叉堆堆顶元素的索引已经不在滑动窗口的范围中时,即
q[0][1] <= i - k
时,不断删除堆顶元素,直到最大值元素的索引在滑动窗口的范围中。 - 将最大值加入到答案数组中,继续向右滑动。
- 滑动结束时,输出答案数组。
思路 1:代码 #
|
|
思路 1:复杂度分析 #
- 时间复杂度:$O(n \times \log_2n)$。
- 空间复杂度:$O(k)$。