滑动窗口
遇到滑动窗口的问题，在编码时，可以有生产者-消费者的建模。 后面结合一些题来细讲。并探究一下这类题的本质。
本质
滑动窗口是一种使用区间局部性与连续性来减小搜索空间的方法。往往能将 $O(n^2)$ 的区间枚举优化到线性复杂度。算法本身由以下要素组成：
- 窗口标记。即窗口头尾指针。
- 窗口滑动、伸缩策略。往往是与区间信息相关的贪心。
- 特定的窗口区间信息。
窗口标记
窗口的标记保证了算法的线性复杂度。因为两个指针加起来最多移动 $2n$ 次嘛（都只会右移）。
窗口左指针往往负责缩小区间，右指针负责扩大区间。
窗口策略
窗口滑动和伸缩的策略要分两种情况考虑。第一种是窗口为固定长度，这种情况比较简单，窗口仅仅滑动就行了；第二种是窗口伸缩。窗口如何伸，如何缩的策略，往往是依赖窗口区间信息的约束来确定的贪心策略。
区间信息 - 连续性
窗口的区间信息要满足连续性的特点。即区间 $[a,b]$ 的信息，可以在与区间长度无关的复杂度下推导出相邻区间 $[a-1, b]$ 或 $[a,b+1]$ 的信息。而且如果要直接获取某个区间的信息，需要付出区间长度的复杂度的代价。
比如区间和。直接计算 $sum(a, b)$，时间 $O(b-a)$。但是通过 $sum(a,b-1) + arr[b]$，需要 $O(1)$。
这是我一开始写出的性质。看完本文后，请你再来想想这一条连续性是必要的吗？ 答案是不必要。不然这两行话才是不必要的那个。
区间信息 - 单调性
同时，区间信息和区间长度满足单调性。对任意区间，长度扩展后的信息一定是单向增大或减小的。（当然这个信息不一定就是一个数。这里只是当成一个可比较的抽象概念来解释）。还是区间和的例子，当所有数都大于 0 时，对任意一个区间，扩张总是会使得区间和变大。也就是满足单调性。
所以大部分情况下可以用生产者和消费者的模型来建模窗口伸缩的策略。
为什么滑动窗口能降低复杂度至线性？
大部分会回答：因为指针只能移动那么多次。但这个答案显然没有触及滑动窗口的核心。
初识搜索空间
以一个具体问题为例：长度最小的子数组
样例一：2, 3, 1, 2, 4, 3；target=7
我们不妨来看看搜索空间的图。图的每一个节点代表搜索空间的一个区间，向右下的有向边代表区间向右扩大一个元素，向左下代表收缩一个元素。忽略空区间。
这个搜索空间本身有一些有趣的性质。可以多加观察行的规律、列的规律、斜对角线的规律
我们将区间和大于 target=7 的节点用绿色标出来，小于的用红色标出来。
发现了么？二者的分布是有规律的，可以同一条线分开。
导致了这个规律的原因是区间和这一“区间信息”的单调性。右下的区间和一定比左上的高。我们的滑动窗口在搜索时实际上就一直在条分界线上左右横跳。
所以，滑动窗口是利用了区间信息的单调性，将搜索空间缩小到了分割线两边的节点上。你可以算算，无论怎么画分割线，其两边的节点数之和不会超过 $2n$。这也印证了区间两端节点移动次数之和不会超过 $2n$。
再看区间信息
区间和这一类“区间信息”，是滑动窗口最常见的单调性。这种单调性的搜索空间往往能用一条上面的图中的分割线来划分合法空间和非法空间。
我称之为“线性单调性的区间信息”。那么也一定有非线性的。
比如下面这几道题：
三道题的核心思想是利用一个 diff 变量来判断当前子串和目标子串的字符差异数。我们要在搜索空间找到 diff 最小或者为 0 的区间，此时搜索区间的样子和前面区间和就不一样了。
不过仍然具有单调性，所以仍然用滑动窗口来做。
实用主义最爱
别废话，什么时候该用滑窗，用的时候有哪些注意？
什么时候用
- 区间问题
- 区间的信息有单调性
- 最常见的单调性是，区间信息随着区间长度单调变化
- 另一种“子字符串”式的单调性，需要从区间信息极值处向外考虑
- 其他的还没遇见过
注意
- 最常见的单调性，可以用生产者消费者理解。将区间的信息视作一种资源，区间的收缩与扩张视作生产与消费（没说收缩一定对应生产哦）。
- 统计满足条件的最小区间时，可以剪枝。只要比当前局部最小的答案更长的区间直接剪掉。
- 还有一类题是统计区间个数。这个就是简单的数学问题了。
奖励你写力扣
This one is tricky