滑动窗口

滑动窗口

🟧概述

🔻含义： 使用一个零时变量记录过程值 当这个过程值满足题目要求时候 就收敛窗口直到过程值不满足题目要求 否则一直扩大窗口统计值

🔻试用场景： 查找连续正数数组或字符串以及子数组、子串问题

🔻时间复杂度： O(n²)->O(n)

🔻空间复杂度： O(n)

🔻注意事项：

🔸满足滑动窗口的单调性

🔸过程变量的选择(数组、普通变量、容器) 收敛扩大窗口的时机(题意)

🔸收敛窗口的移动(++l)

🔸收敛窗口的条件(LIMIT)

🔸答案是最大值还是最小值(题意)

🔸统计答案的位置(个数还是长度)

🟧模板

📌通用模板

class Solution {
    public int Window(int[] nums) {
          int limit=???;
          int len = nums.length;
          int temp=0;/int[]temp= new int[128];/Map temp= new HashMap();
          int res=0;
          int l=0;
          int r=0;

            while(r<len){

                //限定条件下对temp进行增益;
                ++temp; // temp+=nums[r];

                //满足题目要求 就收敛窗口    temp和limit(根据题目意思来)的相对关系
                while(temp???limit){ //内部循环的值 和前面的值 以及给定的limit相关
                    //限定条件下对temp进行减益;
                    --temp;
                    ++l;
                }

                //结果统计返回
                int curLen = r-l+1;
                res = Math.min/max(res,curLen); res+=r-l+1;

                ++r;
            }

       return res;
  }
}

🟧总结

🔻思考1:为什么滑动窗口能避免暴力搜索?

🔸总的来说两个循环之间没有直接的关系 暴力的嵌套循环，维护了一个窗口，但是它窗口需要外层循环指定窗口起始位置内层循环遍历窗口元素，并计算窗口所求值

而滑动窗口的窗口，可以通过前一个窗口弃掉第一值，加入后一个新值得到，通过前一个窗口得到后一个窗口，利用这种关联关系避免嵌套循环

🔻思考2:滑动窗口本质?

🔸滑动窗口本质上来源于单调性，一般可以理解为，随着左端点位置的增加，其最优决策的右端点位置单调不减 利用决策单调性来实现复杂度优化

🔸破坏 右端点单调性的条件都会导致 滑动窗口不适用 比如 数组中的数有负数等·····

🔻思考3:滑动窗口实际应用?

🔸TCP的流量控制：维护一个发送窗口 窗口不断扩大达到最大窗口长度就不再扩大 当收到一个ack就缩小窗口 此过程是动态的

🔻思考4:滑动窗口的限制条件?

🔸理清楚 limit的含义 边界是什么

🔻思考5:滑动窗口什么时候扩大?

🔸temp累计结果 始终不满足 limit 就扩大

🔻思考6:滑动窗口什么时候缩小?

🔸temp累计结果 始终满足 limit 就缩小

🔻思考7:统计答案?

🔸什么位置统计答案? 外while 还是内while

🔸统计答案的方式? 求最大值/最小值/统计个数