模版 - 滑窗

滑动窗口

• 模版总结

  • 一定是条件满足时，更新最终结果
  • 首先最外部的循环while (j < len)
  • 接着内部有一个while循环，需要在里面压缩i
    • 条件成立进while：最小窗口；更新值；更新条件；i++
    • 条件不成立进while：最大窗口；更新条件；i++；「在外面更新值」
  • 接着走出while循环
    • j++
  • 注意与定长滑动窗口的区别！！！

• 破题思路：窗口应该满足什么条件 or 不满足什么条件！！！

• 904.水果成篮，结合题解，深入理解：

  • 最大滑动窗口 - 模版

    while j < len(nums):
        // 判断[i, j]是否满足条件
        while 不满足条件：
            i += 1 //（最保守的压缩i，一旦满足条件了就退出压缩i的过程，使得滑窗尽可能的大）
        // 不断更新结果（注意在while外更新！）
        j += 1

  • 最小滑动窗口 - 模版

    while j < len(nums):
        // 判断[i, j]是否满足条件
        while 满足条件：
            // 不断更新结果(注意在while内更新！)
            i += 1 //（最大程度的压缩i，使得滑窗尽可能的小）
        j += 1

  • 确实，有了模版后，遇到滑窗问题，思路更加清晰了
    • 破题思路：窗口应该满足什么条件 or 不满足什么条件！！！
    • 最大窗口：2024. 考试的最大困扰度
    • 最小窗口：1234. 替换子串得到平衡字符串
      • 这个题目还是比较难，需要好好思考转换一下思路！！！
      • 窗口应该满足：包含的多的字符的个数应该 >= 需要替换的个数
    • 定长窗口：438. 找到字符串中所有字母异位词
      • ⚠️ 定长窗口的题目中，套用模版时要注意一下啊！！！

• 1838.最高频元素的频数

  • 需要动脑思考一下，察觉为使用滑动窗口
  • 而且在做减法的时候有一个溢出问题：啊啊啊啊啊！！！