滑动窗口最大值

Tips

题目类型: 滑动窗口, 单调队列

题目

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

题解

直观解法

像我这种垃圾, 菜鸡, 废物一开始肯定会这么写, 心里还在嘲笑一道 hard 为什么简单, 直到提交的时候告诉我 Time Limit Exceeded.

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number[]}
 */
var maxSlidingWindow = function (nums, k) {
  let left = 0,
    right = k

  const res = []

  while (right <= nums.length) {
    const sub = nums.slice(left, right)
    const max = Math.max(...sub)
    res.push(max)
    left++
    right++
  }

  return res
}

优雅解法

使用单调队列, 单调队列是一种特殊的队列, 它保持队列中的元素单调递增或单调递减. 在本题中, 我们需要一个单调递减队列, 队列中存储的是数组的下标, 而不是数值本身.

遍历数组 nums:

维护队列的单调性: 从 deque 的队尾开始, 如果队尾元素对应的数值小于当前元素 nums[i], 则将队尾元素移除, 直到队列为空或者队尾元素对应的数值大于等于 nums[i]. 这样可以保证队列中的元素是单调递减的.
添加当前元素的下标: 将当前元素的下标 i 添加到 deque 的队尾.
移除超出窗口范围的下标: 如果 deque 的队头元素(即最左边的元素)的下标小于 i - k, 则将其移除, 因为它已经不在当前窗口内了.
记录最大值: 当 i >= k - 1 时, 说明已经形成了一个完整的窗口, 此时 deque 的队头元素对应的数值就是当前窗口的最大值. 将其加入结果数组.

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number[]}
 */
var maxSlidingWindow = function (nums, k) {
  // deque 中存储的是 nums 中每个元素的下标
  const dq = []
  const maxes = []
  const n = nums.length

  for (let i = 0; i < n; i++) {
    // 如果队列不为空且队尾对应的元素小于当前遍历到的值,
    // 则弹出当前队尾, 直到队尾没有小于 i 所对应的元素,
    // 这样就确保了队首对应的元素始终是最大的.
    while (dq.length > 0 && nums[dq[dq.length - 1]] <= nums[i]) dq.pop()

    // 队尾弹入 i
    dq.push(i)

    // 如果队首所对应的元素不在窗口内, 则弹出
    if (dq[0] <= i - k) dq.shift()

    // 只有当 i 大于等于窗口大小时才能写入窗口的最大值
    if (i >= k - 1) maxes.push(nums[dq[0]])
  }

  return maxes
}

题目​

题解​

直观解法​

优雅解法​

题目

题解

直观解法

优雅解法