滑动窗口与双指针

Amroning / 2024-12-29 / 原文

1.定长滑动窗口套路

参考:灵神的总结

入-更新-出:

入: 下标为 i 的元素进入窗口,更新相关统计量。如果 i<k−1 则重复第一步。
更新: 更新答案。一般是更新最大值/最小值。
出: 下标为 i−k+1 的元素离开窗口,更新相关统计量。

for(int i=0;i<nums.size();++i){
    //1.进入窗口操作,比如:
    cnt+=nums[i];
    
    //如果目前窗口大小不足指定窗口大小,就continue(就是刚开始遍历的时候,窗口大小都是从1开始的,注意下标从0开始,所以下面判断是k-1)
    if(i < k - 1)
        continue;
    
    //2.到这里肯定是窗口大小,可以求答案了,比如这里求个窗口最大值:
    ans = max(ans, cnt);
    
   //3.最后让窗口中的第一个元素离开窗口:
    cnt -= num[i - k + 1];    
}