欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

一文搞定滑动窗口算法

程序员文章站 2022-07-13 08:57:10
...

滑动窗口构成

滑动窗口问题一般3要素和1个求值条件:
要素:

  • 快指针fast
  • 慢指针slow
  • 资源值(一般随着fast右移减少,slow左移增多)

求值条件:

求最大值时:

  1. 满足条件前提下,fast要尽可能的扩展,记录资源消耗,扩展过程中slow不进行收缩;
  2. 一旦资源消耗完,用while进入slow右移来释放资源(使用while的原因是fast到最右边,slow需要继续右移完成循环);
  3. 优化技巧【动态(尽可能消耗)+固定窗口(保持资源为0)】:
    因为fast尽可能扩展后,下一个元素必定是消耗K。slow右移动增加K,fast右移动消耗K,刚好抵消。
    所以当slow右移释放资源时,fast可以同时右移占用资源,即slow和fast同时移动,使得资源一直存有被消耗完的状态来减少循环次数。
    动态+固定窗口求最大值

求最小值时:

  1. 初始时,fast尽可能右移,
  2. 当滑动窗口内的数据满足条件的边界时,slow进行收缩,fast保持不变。
  3. 在slow收缩过程求最小值
    动态窗口求最下值
  • 求最小值通用代码模板如下: *
//  定义退出条件
while(fast >= slow && fast < len){
        //fast指针右移
        // 记录资源消耗,
        while(// 资源消耗完的条件){
            //slow右移
            //释放消耗的资源
            //记录fast和slow之间的长度,返回最小区间
        }
 }
        return min;

总结

  1. 不管是求最大或最小问题,fast必定是满足条件的情况下尽可能往右移动。
  2. slow的移动方式分最大和最小问题讨论
  • 最大区间:
    slow左移停止的条件是fast可以发送右移(打破区间符合条件的情形),继续计算更多的结果,来比较获得最大区间。
  • 最小区间:
    区间符合条件的情形前提,slow尽量右移,缩小区间来换取最小区间,同时取得fast右移来遍历更多的可能结构。
  1. slow右移(增加资源)在求最大区间和最小区间时有一个共同作用:打破区间符合条件的情形(资源剩余),使得fast继续右移(尽量消耗资源)以获得更多为遍历情形中可能出现的结果。

字节内推点击

相关标签: 算法 java