239. 滑动窗口最大值 🟥

题目

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]

题解

单调递减队列

时间复杂度：O(N)

for 里面嵌套了 while 就觉得是 O(N²)，这是错误的！
请注意，每个元素最多只会入队一次，出队一次。总操作次数是 2N，所以时间复杂度是绝对的 O(N)。
空间复杂度：O(K)

var maxSlidingWindow = function (nums, k) {
  const result = []
  // 双端队列，存储的是元素的【索引】！(用来判断是否过期)
  const deque = []

  for (let i = 0; i < nums.length; i++) {
    console.log('♻️ i', i, '【', nums[i], '】')
    console.log('deque', deque.map(index => nums[index]).join(', '))

    // 1. 清理过期元素
    // 队列头部的索引如果已经滑出了当前窗口 [i - k + 1, i]，就把它踢掉
    if (deque.length > 0 && deque[0] <= i - k) {
      deque.shift()
    }

    // 2. 保持单调递减
    // 如果新来的 nums[i] 大于等于队列尾部的元素，尾部元素直接被淘汰出局
    while (deque.length > 0 && nums[i] >= nums[deque[deque.length - 1]]) {
      deque.pop()
    }

    // 3. 入列
    deque.push(i)

    console.log('deque', deque.map(index => nums[index]).join(', '))

    // 4. 记录当前窗口的最大值
    // 只有当窗口完全形成时（i 走到 k-1 及以后），才开始收集结果
    if (i >= k - 1) {
      result.push(nums[deque[0]]) // 队头永远是当前窗口的老大
    }
  }

  return result
}

console.log('🌰', maxSlidingWindow([1, 3, -1, -3, 5, 3, 6, 7], 3))
console.log('-------')
console.log('🌰', maxSlidingWindow([1, 3, -1, -3, 5, 3, 2, 2], 3))

执行结果

♻️ i 0 【 1 】
deque 
deque 1
♻️ i 1 【 3 】
deque 1
deque 3
♻️ i 2 【 -1 】
deque 3
deque 3, -1
♻️ i 3 【 -3 】
deque 3, -1
deque 3, -1, -3
♻️ i 4 【 5 】
deque 3, -1, -3
deque 5
♻️ i 5 【 3 】
deque 5
deque 5, 3
♻️ i 6 【 6 】
deque 5, 3
deque 6
♻️ i 7 【 7 】
deque 6
deque 7
🌰 [ 3, 3, 5, 5, 6, 7 ]
-------
♻️ i 0 【 1 】
deque 
deque 1
♻️ i 1 【 3 】
deque 1
deque 3
♻️ i 2 【 -1 】
deque 3
deque 3, -1
♻️ i 3 【 -3 】
deque 3, -1
deque 3, -1, -3
♻️ i 4 【 5 】
deque 3, -1, -3
deque 5
♻️ i 5 【 3 】
deque 5
deque 5, 3
♻️ i 6 【 2 】
deque 5, 3
deque 5, 3, 2
♻️ i 7 【 2 】
deque 5, 3, 2
deque 3, 2
🌰 [ 3, 3, 5, 5, 5, 3 ]

本页目录

题目

题解