滑动窗口应用场景
关键词:
满足xxx条件(计算结果,出现次数,同时包含)
最长/最短
子串/子数组/子序列
例如:长度最小的子数组
滑动窗使用思路(寻找最长)
核心:左右双指针(L,R)在起始点,R向右逐位滑动循环
每次滑动过程中
如果:窗内元素满足条件,R向右扩大窗口,并更新最优结果
如果:窗内元素不满足条件,L向右缩小窗口
直到R到达结尾。
例子:寻找队列里面最长的红球数量
首先滑动右指针,发现有一个红球,更新最大的数量Max为1,然后接着右移;
右移之后,发现没有更新最大值,那么就把左指针进行更新,左指针往右移;
左指针右移到与右指针重复的位置,进行右指针更新;
右指针接着往右移,右移的过程中发现,最大值得到更新,更新至3,一直移动到无法更新指针的为止,这时候该移动左指针;
同理移动左指针到与右指针重合;
按照上述方法继续移动右指针;
按照上述方法继续移动左指针,直至在左右指针达到最后点,循环完成。