leetcode 239题 滑动窗口最大值
给定一个数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。
返回滑动窗口中的最大值。
进阶：
你能在线性时间复杂度内解决此题吗？
示例
输入: nums = [1,3,-1,-3,5,3,6,7], 和 k = 3
输出: [3,3,5,5,6,7]
解释:
滑动窗口的位置 最大值
--------------- -----
[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
思路
利用双端队列
维持单调递减队列
- push 操作，如果队列里面还有比插入的数更小的元素时，先删除更小的数，直到没有更小的数，再插入到队列
- pop 操作，确保队列里面push没有更小的数，判断是否是头部最大的元素，若是就删除头部元素
代码
class SlideWindow {
constructor() {
this.data = [];
}
push(val) {
while (this.data.length > 0 && this.data[this.data.length - 1] < val) {
this.data.pop();
}
this.data.push(val);
}
pop(val) {
if (this.data.length > 0 && this.data[0] === val) {
this.data.shift();
}
}
max() {
return this.data[0];
}
}
function maxSlidingWindow(nums, k) {
let res = [];
const windows = new SlideWindow();
for (let i=0; i<nums.length; i++) {
if (i + 1 < k) {
windows.push(nums[i]);
} else {
windows.push(nums[i]);
res.push(windows.max());
windows.pop(nums[i-k+1]);
}
}
return res;
}
复杂度分析
- 时间复杂度: O(N)
- 空间复杂度: O(N)