理解滑动窗口

发布于 2024-05-01 14:16:54| 分类于 数据结构和算法

滑动窗口算法技巧主要用来解决子数组/子串问题，比如让你寻找符合某个条件的最长/最短子数组。

由于子数组都是数组中连续的元素，因此可以使用滑动窗口

思路

滑动窗口要注意的也是窗口区间的含义，决定什么时候移动左边的窗口，什么时候移动右边的窗口，窗口采用的是左闭右闭还是左闭右开

比如下面这个求二进制数组中连续相同数字最长长度，使用的是一个[l,r]的窗口，

• 每轮循环都会移动r
• 当nums[l] !== nums[r]的时候，就会移动l，保证窗口保存的都是相同的数字
• 在每轮循环中保存窗口长度的最大值

function walk(nums) {
  const n = nums.length
  let l = 0
  let r = 0
  let ans = 0
  while (r < n) {
    if (nums[l] != nums[r]) {
      l = r
    }
    ans = Math.max(r - l + 1, ans)
    r++
  }
  return ans
}
var nums = [0, 1, 0, 0, 0, 1, 1, 0]
var ans = walk(nums, target) // 3

滑动窗口的细节就在于什么时候移动窗口，不同的题目有很多变种，其中又涉及到不少细节，需要多加练习。

2024. 考试的最大困扰度

2024. 考试的最大困扰度

// 维护区间中另外一种字符的长度
var maxConsecutiveAnswers = function (answerKey, k) {
    const n = answerKey.length

    function walk(target) {
        let l = 0
        let r = 0
        let cnt = 0
        let ans = 0
        while (r < n) {
            const ch = answerKey[r]
            r++
            if (ch !== target) {
                cnt++
            }
            while (cnt > k) {
                if (answerKey[l] !== target) {
                    cnt--
                }
                l++
            }
            ans = Math.max(ans, r - l)
        }
        return ans
    }

    return Math.max(walk('T'), walk('F'))
};

#滑动窗口

你要请我喝一杯奶茶？

版权声明：自由转载-非商用-保持署名和原文链接。

本站文章均为本人原创，参考文章我都会在文中进行声明，也请您转载时附上署名。