滑动窗口最大值

题目

题目来源：力扣（LeetCode）

给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。
返回滑动窗口中的最大值。

示例 1：

输入：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

示例 2：

输入：nums = [1], k = 1
输出：[1]

示例 3：

输入：nums = [1,-1], k = 1
输出：[1,-1]

示例 4：

输入：nums = [9,11], k = 2
输出：[11]

示例 5：

输入：nums = [4,-2], k = 2
输出：[4]

思路分析

1. 这道题可以使用单调队列来解决，我们维护一个单调递减的队列，将当前滑窗中的元素下标 依次加入到队列中
2. 遍历给定数组中的元素，如果队列不为空且当前考察元素大于等于队尾元素，则将队尾元素移除。直到，队列为空或当前考察元素小于新的队尾元素，将当前考察元素加入到队列中；
3. 当队首元素的下标小于滑动窗口左侧边界left时，表示队首元素已经不在滑动窗口内，因此将其从队首移除。
4. 由于数组下标从0开始，因此当窗口右边界right+1大于等于窗口大小k时，意味着窗口形成。此时，队首元素就是该窗口内的最大值。 ```javascript /**
   • @param {number[]} nums
   • @param {number} k
   • @return {number[]} */

// 思路 // 遍历给定数组中的元素，如果队列不为空且当前考察元素大于等于队尾元素，则将队尾元素移除。直到，队列为空或当前考察元素小于新的队尾元素； // 当队首元素的下标小于滑动窗口左侧边界left时，表示队首元素已经不再滑动窗口内，因此将其从队首移除。 // 由于数组下标从0开始，因此当窗口右边界right+1大于等于窗口大小k时，意味着窗口形成。此时，队首元素就是该窗口内的最大值。

var maxSlidingWindow = function(nums, k) { // 存储窗口中的最大值 const res = []; // const queue = []; // 遍历数组中元素，right 表示滑动窗口右边界 for (let right = 0; right < nums.length; right++) { // 如果队列不为空且当前考察的元素大于等于队尾元素，则将队尾元素删除 // 直到队列为空或当前考察元素小于新的队尾元素时，往队列添加元素 while(queue.length && nums[right] >= nums[queue[queue.length - 1]]) { queue.pop() // 将队尾元素移除 }

// 存储元素在 nums 中的下标
queue.push(right);
// 计算窗口左侧边界
let left = right - k + 1;
// 当队首元素的小标小于滑动窗口左侧边界left(下标) 时
// 表示队首元素已经不在活动窗口内，因此将其从队首移除
while (queue[0] < left) {
  queue.shift()
}
// 由于数组下标从 0 开始，因此窗口右边界 right + 1 大于等于窗口大小 k 时，意味着窗口形成，
// 此时，队首元素就是该窗口内的最大值
if (right + 1 >= k) {
  res[left] = nums[queue[0]]
}

}

return res }; ```