leetcode - 滑动窗口

[Caaalabash]

滑动窗口

作为一个前端开发，目前仅在记忆面试题的"TCP滑动窗口"中遇到了这几个字，实际开发中，暂未遇到。

本篇从选取leetcode上10道题，做一个小总结。

leetcode 1004

题解思路：

我愿称之为滑动窗口的标准模版题

k是窗口合法的限定条件。从0开始，每次right指针向右移动一位，判断窗口是否合法：

• 如果不合法：while循环右移left指针，直到窗口合法
• 如果合法：记录窗口大小，继续右移right指针

实现：

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

解题思路：

我愿称之为滑动窗口的标准模版题，参考 1004 题即可

实现：

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 1423

解题思路：

固定大小窗口，维护一个大小为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 1456

解题思路：

固定大小窗口，维护一个大小为k的窗口，求这个窗口向右滑动的过程中能取得的最大值，本质上，同1423题

实现：

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 1658

解题思路：

可变大小窗口，寻找一个连续窗口，窗口内元素和 = sum - x，本质上类似于1423、1456题

实现：

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 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 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 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
      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
}