滑动窗口
# 滑动窗口
滑动窗口有两大类
固定长度的滑动窗口:窗口的大小是固定好的,这是其实分为了窗口形成和人窗口滑动两个过程,窗口形成就是要先让窗口达到要求的长度; 窗口滑动的过程在右边界长的时候,左边界也要跟着长,维持窗口长度不变;
可变长度的滑动窗口:这也是遇到最多的,控制窗口移动的原因不是长度,而是是否达到题目中某一条件,如果达到此条件,那右边界停下,左边界开始移动,试图去破坏这一条件,就是在这个过程中不断的更新结果。
滑动窗口的应用场景有几个特点:
需要输出或比较的结果在原数据结构中是连续排列的;
每次窗口滑动时,只需观察窗口两端元素的变化,无论窗口多长,每次只操作两个头尾元素,当用到的窗口比较长时,可以显著减少操作次数;
窗口内元素的整体性比较强,窗口滑动可以只通过操作头尾两个位置的变化实现,但对比结果时往往要用到窗口中所有元素。
更新时间: 1/17/2022, 8:54:37 PM