滑动窗口
简介
滑动窗口算法可以解决数组字符串的连续子数组/子串问题。通常采用一个大小可变的窗口在某字符串或数组上滑动，来匹配每个窗口内的元素是否满足某种条件。
具体滑动策略：
一个right指针， 一个left指针，right一直向右滑动，然后每向右滑动一个元素，都判断一下当前窗口是个可以收缩。如果可以收缩，那么就向右移动left指针。
窗口的数据结构：应根据各种数据结构的特点来选取
- 哈希表，collectiond.defaultdict
- 优先队列，heapq
- 单调队列，deque
- 有序列表，SortedList
应用条件：
原数据必须满足单调性，即需要明确知道什么时候扩张什么时候收缩。例如560. 和为 K 的子数组原数据中含有负数，破坏了单调性，收缩与扩张条件就不明确了。
思考（也是考点）：
- 窗口使用什么数据结构？
- 达到窗口限定后，左边届该怎样收缩，如果无法以常规方法收缩，考虑延时删除策略（在采集答案前进行）如 727.最小窗口子序列
- 怎样采集答案
- 滑窗的步长
- 滑窗的起始位置
- 是否需要数据预处理，例如排序，才能使用滑窗
滑动窗口是在数组/字符串中间滑动，那如果要取边上的怎么办？见1428 和 1653
一方面可以 采用旋转数组的思路，只需要在采集答案的时候特判一下right和left指针需要在原数组边界取到；
另一方面：可以转化思路，使得答案可以通过滑动中间的窗口转化得到。
涉及到窗口中最大值于最小值中位数等的题目，可以考虑红黑树（有序数组），但是如果只用到最大值，那就不需要有序数组
题型
基础模板题
滑窗匹配第二个字符串
窗口内字符无顺序的 和 有顺序的。无顺序的可以用hashmap来存储窗口内的字符，有顺序的就不行了！只能再来一个指针匹配第二个字符串，例 727.最小窗口子序列
727. 最小窗口子序列 从右边往左收缩的
计算子数组个数；动态规划规思想 + 滑窗
考点1：借鉴动态规划的思想，使用 right - left 来表示增加的子数组个数，即新来的数字nums[right] 可以新增加 right - left 个子数组
考点2：求区间内 某个属性 刚好 等于 k的子数组数量。属性刚好等于k的子数组数量 其实是不好求的，因为窗口在收缩的时候，这个属性是不增的，所以求 属性不超过 k 的子数组数量 更直观容易一点。 然后 再求 属性不超过 k-1 的子数组数量，最后做差即可。
滑动窗口 + 有序列表（红黑树）
239. 滑动窗口最大值 或者用单调队列
技巧题
滑动窗口完整笔记参见 滑动窗口
727. 最小窗口子序列 （字符串匹配，有序匹配）
76. 最小覆盖子串 （字符串匹配，无序匹配）
795. 区间子数组个数 （右区间-左区间）