力扣239-滑动窗口中的最大值

原题

给你一个整数数组 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]


提示：

1 <= nums.length <= 105
-104 <= nums[i] <= 104
1 <= k <= nums.length

解题思路

理解题目逻辑：窗口长度为 k，获取该窗口下最大的值，窗口收缩会出现多个可能的子集，在子集中找到最大的值

1. 遍历数组 nums，循环执行条件是 r < nums.length
2. 每次移动右侧指针时，将 nums[r] 与存储最值得队列尾巴对比，如果队列的尾部元素小于 nums[r]，一直将队列尾部出队直到尾部元素大于 nums[r]
3. 一旦 r - l + 1 > k即窗口长度超过k，需要收缩 l（l++），收缩之前判断 num[l] 是否和队列头部元素相等，如果相等，出队队列头部元素

PS: 出队头部元素不关注 nums[l] 在队列中部或者尾部的情况，因为有新的 nums[r] 大于队列除了队头以外的任意一个值，队列内的元素都有可能被出队 或者简单记忆（只关注最大值）

4. 移动右指针之前将队头的值存储待定结果集
5. 返回结果集中的最大值

错误点：

1. 将不符合的窗口区间也记录下来了（一定确保 [l,r] 窗口要合格结果才有效）
2. 区间合格条件需要注意 k 是长度，r 是序列（从0开始），所以区间合格条件是 r >= k - 1

代码

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number[]}
 */
var maxSlidingWindow = function (nums, k) {
  // 窗口长度为 k，一旦窗口长度超过 k，就需要收缩左区间
  // 每次移动右区间，判断区间是否合法，如果合法，更新最大值
  /**
    理解题目逻辑：窗口长度为 k，获取该窗口下最大的值，窗口收缩会出现多个可能的子集，在子集中找到最大的值
 
    1. 遍历数组 nums，循环执行条件是 r < nums.length
    2. 每次移动右侧指针时，将 nums[r] 与存储最值得队列尾巴对比，如果队列的尾部元素小于 nums[r]，一直将队列尾部出队直到尾部元素大于 nums[r]
    3. 一旦 r - l + 1 > k即窗口长度超过k，需要收缩 l（l++），收缩之前判断 num[l] 是否和队列头部元素相等，如果相等，出队队列头部元素

    PS: 出队头部元素不关注 nums[l] 在队列中部或者尾部的情况，因为有新的 nums[r] 大于队列除了队头以外的任意一个值，队列内的元素都有可能被出队
    或者简单记忆（只关注最大值）
 
    4. 移动右指针之前将队头的值存储待定结果集
    5. 返回结果集中的最大值

    错误点：
    1. 将不符合的窗口区间也记录下来了（一定确保 [l,r] 窗口要合格结果才有效）
    2. 区间合格条件需要注意 k 是长度，r 是序列（从0开始），所以区间合格条件是 r >= k - 1

     */
  let l = 0
  let r = 0
  let deque = []
  let res = []
  while (r < nums.length) {
    while (deque.length && nums[r] > deque[deque.length - 1]) {
      deque.pop()
    }
    deque.push(nums[r])
    while (r - l + 1 > k) {
      // 收缩之前判断即将被排除的左端元素是否在单调递减队列头部，若存在，移除该元素
      if (nums[l] == deque[0]) {
        deque.shift()
      }
      // 收缩左侧指针
      l++
    }
    if (r >= k - 1) {
      // 区间合格的时候，队列最大值才有意义
      res.push(deque[0] || 0)
    }
    r++
  }

  return res
}