239. 滑动窗口最大值
239. 滑动窗口最大值
🔴 🔖 队列
数组
滑动窗口
单调队列
堆(优先队列)
🔗 力扣
LeetCode
题目
You are given an array of integers nums
, there is a sliding window of size k
which is moving from the very left of the array to the very right. You can only see the k
numbers in the window. Each time the sliding window moves right by one position.
Return the max sliding window.
Example 1:
Input: nums = [1,3,-1,-3,5,3,6,7], k = 3
Output: [3,3,5,5,6,7]
Explanation:
Window position Max --------------- ----- [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
Example 2:
Input: nums = [1], k = 1
Output: [1]
Constraints:
1 <= nums.length <= 10^5
-10^4 <= nums[i] <= 10^4
1 <= k <= nums.length
题目大意
给你一个整数数组 nums
,有一个大小为 k
的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k
个数字。滑动窗口每次只向右移动一位。
返回 滑动窗口中的最大值 。
解题思路
思路一:双端队列
双端队列(Deque,全称 Double Ended Queue)是一种可以在两端进行插入和删除操作的数据结构。相比于普通的队列(只能在一端插入,在另一端删除),双端队列更加灵活,适用于一些特殊的场景。在 JavaScript 中,双端队列可以使用数组来模拟。
- 遍历数组:每次移动滑动窗口时,对双端队列进行更新:
- 如果队列头部的元素已经不在当前窗口中(即索引小于
i - k + 1
),将其移除。 - 在队列尾部,移除所有小于当前元素的值,因为它们不可能成为当前或之后窗口的最大值。
- 将当前元素的索引加入队列。
- 获取最大值:对于每一个窗口,队列的前端始终保存当前窗口的最大值的索引。
注意:
- 存储数组元素的索引:不会直接存储数组的值,而是存储元素的索引,以便通过索引访问具体的值,并通过索引判断某个元素是否还在当前滑动窗口中。
- 保持队列中的元素单调递减:为了保证队列的前端始终是窗口的最大值,会从队列的后端移除所有小于当前元素的索引。
复杂度分析
- 时间复杂度:
O(n)
,其中n
是数组的长度。每个元素被加入和移除队列至多各一次,因此总的操作次数为O(n)
。 - 空间复杂度:
O(k)
,队列的大小在最坏情况下为k
。
思路二:堆
大顶堆性质:堆是一棵二叉树,每个节点都满足:父节点的值大于左右子节点的值,堆顶元素是当前堆中的最大值。
使用大顶堆来保存滑动窗口中的 k
个数,每次窗口移动时,移除堆中不在当前窗口的元素,并将新元素入堆,堆顶元素就是滑动窗口中的最大值。
复杂度分析
时间复杂度:
O(n × (k + log k))
,这在最坏情况下比使用双端队列的O(n)
时间复杂度要高,尤其当k
接近n
时,复杂度变为O(n × k)
。- 插入操作需要
O(log k)
。 - 删除操作的复杂度为
O(k)
,因为需要遍历堆查找需要移除的元素,然后再执行O(log k)
的调整操作。 - 对于数组中的每个元素,滑动窗口移动时,我们需要进行一次 插入 和一次 删除 操作,数组长度为
n
,因此,最坏情况下总时间复杂度为O(n * (k + log k))
。
- 插入操作需要
空间复杂度:
O(k)
,堆中的最大元素个数为k
。
代码
/**
* @param {number[]} nums
* @param {number} k
* @return {number[]}
*/
var maxSlidingWindow = function (nums, k) {
let deque = [],
res = [];
for (let i = 0; i < nums.length; i++) {
if (deque.length && deque[0] < i - k + 1) {
deque.shift();
}
while (deque.length && nums[deque[deque.length - 1]] < nums[i]) {
deque.pop();
}
deque.push(i);
if (i >= k - 1) {
res.push(nums[deque[0]]);
}
}
return res;
};
/**
* @param {number[]} nums
* @param {number} k
* @return {number[]}
*/
var maxSlidingWindow = function (nums, k) {
let maxHeap = new MaxHeap(),
res = [];
for (let i = 0; i < k; i++) {
maxHeap.insert(nums[i]);
}
res.push(maxHeap.heap[0]);
for (let i = 0; i < nums.length - k; i++) {
maxHeap.remove(nums[i]);
maxHeap.insert(nums[i + k]);
res.push(maxHeap.heap[0]);
}
return res;
};
class MaxHeap {
constructor() {
this.heap = [];
}
insert(value) {
this.heap.push(value);
this.heapifyUp(this.heap.length - 1);
this.heapifyDown(0);
}
remove(value) {
const index = this.heap.indexOf(value);
if (index !== this.heap.length - 1) {
this.heap[index] = this.heap.pop();
this.heapifyDown(index);
} else {
this.heap.pop();
}
}
heapifyUp(i) {
while (i) {
const parent = ((i - 1) / 2) | 0;
if (this.heap[parent] < this.heap[i]) {
[this.heap[parent], this.heap[i]] = [this.heap[i], this.heap[parent]];
i = parent;
} else {
break;
}
}
}
heapifyDown(i) {
let left = i * 2 + 1,
right = i * 2 + 2,
min = i;
if (this.heap[min] < this.heap[left]) {
min = left;
}
if (this.heap[min] < this.heap[right]) {
min = right;
}
if (min !== i) {
[this.heap[min], this.heap[i]] = [this.heap[i], this.heap[min]];
this.heapifyDown(min);
}
}
}
相关题目
题号 | 标题 | 题解 | 标签 | 难度 |
---|---|---|---|---|
76 | 最小覆盖子串 | [✓] | 哈希表 字符串 滑动窗口 | |
155 | 最小栈 | [✓] | 栈 设计 | |
159 | 至多包含两个不同字符的最长子串 🔒 | 哈希表 字符串 滑动窗口 | ||
265 | 粉刷房子 II 🔒 | 数组 动态规划 | ||
1696 | 跳跃游戏 VI | 队列 数组 动态规划 2+ | ||
2398 | 预算内的最多机器人数目 | 队列 数组 二分查找 4+ | ||
2517 | 礼盒的最大甜蜜度 | 贪心 数组 二分查找 1+ | ||
2530 | 执行 K 次操作后的最大分数 | [✓] | 贪心 数组 堆(优先队列) |