blog-frontend leetcode - 滑动窗口题目总结

leetcode - 滑动窗口题目总结

Open Caaalabash opened this issue 3 years ago • 0 comments

滑动窗口

滑动窗口的本质是双指针，使用left指针和right指针构成一个窗口。窗口应有如下特点：

窗口中的元素关系满足题目给出的某个限定条件
一个合法的窗口可以向题目提供一个可能的解

一般来说，窗口类型和指针初始值索引关系如下：

固定大小窗口（设大小为 k）：left = 0, right = k-1
不定大小窗口：left = 0, right = 0

left和right指针移动方式：

right指针：主动右移
left指针：当[left, right]构成的窗口不符合要求时，被动右移

滑动窗口的基本解题模板为：

// nums是给定区间，通常k是一个窗口限定条件
function slidingWindow(nums, k) {
  let result = 0
  let left = 0
  let right = 0
  // 窗口内的某种关系，此处为和
  let sum = 0

  while (right < nums.length) {
    // 维护窗口内的某种关系
    sum += nums[right]
    // 窗口中的元素关系不满足题目给出的某个限定条件时，左指针被动右移
    while (sum < k) {
      // 维护窗口内的某种关系
      sum -= nums[left]
      left++
    }
    // 一个合法的窗口可以向题目提供一个可能的解
    result = Math.max(result, right - left + 1)
    right++
  }

  return result
}

leetcode上，滑动窗口题目分类如下：

基础模版题，作为开胃菜：

1004
1208
1456

模版之上，多了一点变形：

1423
1658
978

组合类型：

1498：滑动窗口 + 数学
3：滑动窗口 + 哈希表
239：滑动窗口 + 单调队列
1438：滑动窗口 + 2个单调队列
480：滑动窗口 + 堆

可以直接点击小标题进入对应的leetcode页面，推荐按着上面的顺序刷题～

leetcode 1004 - 中等

题解思路：

滑动窗口的标准模版题，套模版理解即可

实现：

function longestOnes(nums, k) {
  let result = 0
  let left = 0
  let right = 0

  while (right < nums.length) {
    if (nums[right] === 0) {
      k--
    }
    while (k < 0) {
      if (nums[left] === 0) {
        k++
      }
      left++
    }
    result = Math.max(result, right - left + 1)
    right++
  }

  return result
}

leetcode 1208 - 中等

解题思路：

滑动窗口的标准模版题，套模版理解即可

实现：

function equalSubstring(s, t, maxCost) {
  let result = 0
  let left = 0
  let right = 0

  while (right < s.length) {
    maxCost -= Math.abs(s[right].charCodeAt() - t[right].charCodeAt())
    while (maxCost < 0) {
      maxCost += Math.abs(s[left].charCodeAt() - t[left].charCodeAt())
      left++
    }
    result = Math.max(result, right - left + 1)
    right++
  }

  return result
}

leetcode 1456 - 中等

解题思路：

滑动窗口的标准模版题，套模版理解即可

实现：

function maxVowels(s, k) {
  const vowelsMap = {
    a: 1,
    e: 1,
    i: 1,
    o: 1,
    u: 1
  }
  // 选取前k个作为初始值
  let vowels = 0
  for (let i = 0; i < k; i++) {
    if (s[i] in vowelsMap) {
      vowels++
    }
  }
  let maxVowels = vowels
  // 右移动
  for (let i = k; i < s.length; i++) {
    // 判断进
    if (s[i] in vowelsMap) {
      vowels++
    }
    // 判断出 
    if (s[i - k] in vowelsMap) {
      vowels--
    }
    maxVowels = Math.max(maxVowels, vowels)
  }
  return maxVowels
}

leetcode 1423 - 中等

解题思路：

固定大小窗口

"每次行动，你可以从行的开头或者末尾拿一张卡牌，最终你必须正好拿 k 张卡牌。" 可以转换为维护一个大小为cardPoints.length - k的窗口，求这个窗口向右滑动的过程中能取得的最小值，即可取得剩余卡牌的最大值

实现：

function maxScore(cardPoints, k) {
  const totalSum = cardPoints.reduce((acc, val) => acc += val, 0)
  const windowSize = cardPoints.length - k
  // 选取前 windowSize 个作为初始值
  let sum = 0
  for (let i = 0; i < windowSize; i++) {
    sum += cardPoints[i]
  }
  let minSum = sum
  // 开始向右滑动
  for (let i = windowSize; i < cardPoints.length; i++) {
    // 优化点，求出一进一出的差值
    sum += cardPoints[i] - cardPoints[i - windowSize]
    minSum = Math.min(minSum, sum)
  }
  return totalSum - minSum
}

leetcode 1658 - 中等

解题思路：

可变大小窗口

"每一次操作时，你应当移除数组 nums 最左边或最右边的元素" => 寻找一个连续窗口，窗口内元素和 = sum - x

实现：

function minOperations(nums, x) {
  // 求数组和
  let sum = 0
  for (let i = 0; i < nums.length; i++) {
    sum += nums[i]
  }
  const windowSumTarget = sum - x
  // 如果目标元素和小于0，直接返回
  if (windowSumTarget < 0) {
    return -1
  }
  // 寻找一个连续窗口，窗口内元素和 = sum - x
  let left = 0
  let right = 0
  let operateCount = Number.MAX_VALUE
  let windowSum = 0
  while (right < nums.length) {
    windowSum += nums[right]
    while (windowSum > windowSumTarget) {
      windowSum -= nums[left]
      left++
    }
    if (windowSum === windowSumTarget) {
      operateCount = Math.min(operateCount, nums.length - (right - left + 1))
    }
    right++
  }
  return operateCount === Number.MAX_VALUE ? -1 : operateCount
}

leetcode 978 - 中等

解题思路：

这道题，题目比较难搞懂，但还是一个较为典型的模版题

实现：

function maxTurbulenceSize(arr) {
  let result = 1
  let left = 0
  let right = 0
  
  while (right < arr.length - 1) {
    if (left === right) {
      if (arr[left] === arr[left+1]) {
        left++
      }
      right++
    } else {
      if (arr[right-1] < arr[right] && arr[right] > arr[right+1]) {
        right++
      } else if (arr[right-1] > arr[right] && arr[right] < arr[right+1]) {
        right++
      } else {
        left = right
      }
    }
    result = Math.max(result, right - left + 1)
  }

  return result
}

leetcode 1498 - 中等

解题思路：

经验：涉及到"对10^9 + 7取余"的和幂值的，就先对幂值表进行一次预处理

数学知识：组合数公式的递推公式c(n,0) + c(n,1) + c(n,2) + …… + c(n,n) = 2的n次方

由于子序列不要求连续，那么可以首先排序数组。如果区间[l, r]满足条件nums[l] + nums[r] <= target，那么含有nums[l]的子序列全部满足条件

实现：

function numSubseq(nums, target) {
  // 可以排序
  nums.sort((a, b) => a < b ? -1 : 1)
  // 预处理计算出幂值表
  const pow = [1]
  for (let i = 1; i < nums.length; i++) {
    pow[i] = (pow[i-1] << 1) % 1000000007
  }
  let count = 0
  let left = 0
  let right = nums.length - 1
  while (left <= right) {
    if (nums[left] + nums[right] > target) {
      right--
    } else {
      // 组合数公式
      count = (count + pow[right - left]) % 1000000007
      left++
    }
  }
  return count
}

leetcode 3 - 中等

解题思路：

滑动窗口 + 哈希表记录首次出现的索引位置

实现:

function lengthOfLongestSubstring(s) {
  if (!s) {
    return 0
  }
  const counter = {}
  let result = 1
  let left = 0
  let right = 0

  while (right < s.length) {
    if (!(s[right] in counter)) {
      // 记录首次出现索引位置
      counter[s[right]] = right
    } else {
      // 优化点：重复时，left指针移动到首次出现索引的下一个位置
      const oldLeft = left
      left = counter[s[right]] + 1
      // 删除新旧left之间的counter数据
      for (let i = oldLeft; i < left; i++) {
        delete counter[s[i]]
      }
      counter[s[right]] = right
    }
    result = Math.max(result, right - left + 1)
    right++
  }
  return result
}

leetcode 239 - 困难

解题思路：

固定大小窗口，这道题的难点在于：如何在O(1)的时间内算出窗口的最大值，为了解决这个问题，使用了单调队列的数据结构

实现：

function maxSlidingWindow(nums, k) {
  const queue = []
  // 单调栈/队列模版
  // 维护前k个数的单调队列：从队尾到队头单增
  for (let i = 0; i < k; i++) {
    while (queue.length && nums[i] >= nums[queue[queue.length - 1]]) {
      queue.pop()
    }
    // 存放的是索引 
    queue.push(i)
  }

  const result = [nums[queue[0]]]
  let right = k

  while (right < nums.length) {
    // 这里继续维护单调队列
    // 使用 > 也能AC，但是耗时明显增长，为什么？ => queue.shilt() 会调用很多次
    while (queue.length && nums[right] >= nums[queue[queue.length - 1]]) {
      queue.pop()
    }
    queue.push(right)
    // 单调队列队首（最大值的索引）不在范围内的情况
    while (queue[0] <= right - k) {
      queue.shift()
    }
    result.push(nums[queue[0]])
    right++
  }

  return result
}

leetcode 1438 - 中等

解题思路：

这道题的难点在于：如何在O(1)的时间内算出窗口的最大值和最小值，与239题类似

实现：

function longestSubarray(nums, limit) {
  const queMin = []
  const queMax = []
  let left = 0
  let right = 0
  let result = 0

  while (right < nums.length) {
    while (queMax.length && nums[right] > queMax[queMax.length - 1]) {
      queMax.pop()
    }
    queMax.push(nums[right])
    while (queMin.length && nums[right] < queMin[queMin.length - 1]) {
      queMin.pop()
    }
    queMin.push(nums[right])
    // 在239题的基础上，理解到这里应该没问题
    // 此时可以通过queMax[0]取得区间最大值，queMin[0]取得区间最小值，如果他们的绝对差不合法，则需要收缩左区间
    // 收缩左区间时，判断nums[left]与queMax/queMin的关系，维护即可
    while (queMax.length && queMin.length && queMax[0] - queMin[0] > limit) {
      if (nums[left] === queMin[0]) {
        queMin.shift()
      }
      if (nums[left] === queMax[0]) {
        queMax.shift()
      }
      left++
    }
    result = Math.max(result, right - left + 1)
    right++
  }

  return result
}

leetcode 480 - 困难

解题思路：

这是一道相当经典得到的滑动窗口题目，可以说是非常的难了。列举以下几种解法的时间复杂度：

每滑动一次均排序计算中位数：滑动次数为n-k，每次排序的时间复杂度为O(klogk)，总时间复杂度为O(nklogk)
每滑动一次均线性选择计算中位数：滑动次数为n-k，每次选出中位数的时间复杂度为O(k)，总时间复杂度为O(nk)
带有「删除指定元素」操作的双堆：滑动次数为n-k，堆的大小为O(k)，删除堆中元素时间复杂度为O(k)，插入时间复杂度为O(logk)，总时间复杂度为O(nk)
带有「惰性删除元素」的双堆：官方题解，时间复杂度为O(nlogn)
双平衡树：O(nlogk)，涉及到知识盲区了

本题解法是：带有「删除指定元素」操作的双堆，使用双堆的思路可以参考leetcode - 295 数据流中的中位数

实现：

带有「删除指定元素」的堆，如果是java的话，是有这个数据结构的TAT

// 带「删除指定元素」的堆数据结构实现
class Heap {
  constructor(data = [], less) {
    this.data = data
    this.less = less || ((a, b) => a < b)

    if (this.length) {
      for (let p = (this.length - 2) >> 1; p >= 0; p--) {
        this._down(p)
      }
    }
  }
  get length() {
    return this.data.length
  }
  peak() {
    return this.data[0]
  }
  remove(val) {
    let index = -1
    for (let i = 0; i < this.length; i++) {
        if (this.data[i] === val) {
            index = i
            break
        }
    }  
    if (index === -1) return false
    this._swap(index, this.length - 1)
    this.data.pop()
    this._up(index)
    this._down(index)
    return true
  }
  push(val) {
    this.data.push(val)
    this._up(this.length - 1)
  }
  pop() {
    if (!this.length) {
      return
    }
    this._swap(0, this.length - 1)
    const popItem = this.data.pop()
    this._down(0)
    return popItem
  }
  _swap(i, j) {
    [this.data[i], this.data[j]] = [this.data[j], this.data[i]]
  }
  _up(i) {
    if (i <= 0) return
    const pIndex = (i - 1) >> 1
    if (this.less(this.data[i], this.data[pIndex])) {
      this._swap(i, pIndex)
      this._up(pIndex)
    }
  }
  _down(i) {
    let leftIndex = i * 2 + 1
    if (leftIndex >= this.length) {
      return
    }
    if (leftIndex + 1 < this.length && this.less(this.data[leftIndex+1], this.data[leftIndex])) {
      leftIndex++
    }
    if (this.less(this.data[leftIndex], this.data[i])) {
      this._swap(leftIndex, i)
      this._down(leftIndex)
    }
  }
}

295题目，数据流中的中位数拓展：


// MedianFinder 找到数据流中的中位数
class MedianFinder {
  constructor() {
    // 最大堆 存储输入数字中较小的一半
    this.maxHeap = new Heap([], (a, b) => a > b)
    // 最小堆 存储输入数字中较大的一半
    this.minHeap = new Heap([], (a, b) => a < b)
  }
  push(num) {
    if (!this.maxHeap.length || num <= this.maxHeap.peak()) {
      this.maxHeap.push(num)
    } else {
      this.minHeap.push(num)
    }
    this.makeBalance()
  }
  remove(value) {
    if (value <= this.maxHeap.peak()) {
      this.maxHeap.remove(value)
    } else {
      this.minHeap.remove(value)
    }
    this.makeBalance()
  }
  findMedian() {
    if (this.maxHeap.length === this.minHeap.length) {
      return (this.maxHeap.peak() + this.minHeap.peak()) / 2
    }
    return this.maxHeap.peak()
  }
  // 调整两个堆的平衡性
  makeBalance() {
    if (this.maxHeap.length > this.minHeap.length + 1) {
      // 最大堆比最小堆多了两个，pop最大堆的栈顶，push进最小堆
      this.minHeap.push(this.maxHeap.pop())
    } else if  (this.minHeap.length > this.maxHeap.length) {
      // 最小堆比最大堆多，pop最小堆的栈顶，push进最大堆
      this.maxHeap.push(this.minHeap.pop())
    }
  }
}

最终解答

// 如何求出区间内的中位数，参考295
function medianSlidingWindow(nums, k) {
  // 在理解295题的基础上，假设有一个MedianFinder类，可以帮助我们找到中位数
  const medianFinder = new MedianFinder()
  for (let i = 0; i < k; i++) {
    medianFinder.push(nums[i])
  }
  // 找到前k个数字的中位数
  const result = [medianFinder.findMedian()]
  // 继续遍历后面的
  for (let i = k; i < nums.length; i++) {
    // 移除第一个再添加一个
    medianFinder.remove(nums[i - k])
    medianFinder.push(nums[i])
    result.push(medianFinder.findMedian())
  }

  return result
}

参考

参考的一些leetcode题解

480 - 科普一下本题常见解法的时间复杂度

May 17 '21 14:05 Caaalabash

blog-frontend blog-frontend copied to clipboard

leetcode - 滑动窗口题目总结

滑动窗口

参考

blog-frontend
blog-frontend copied to clipboard