算法入门（一）：滑动窗口 之 允许重置的窗口 （Leetcode 485 / 1446 / 674）

允许重置的窗口

例如 Leetcode 485 / 1446 / 674 这类题目，其本质是可变窗口。

• 条件一旦被破坏，左指针直接跳到右指针位置，不逐步收缩
• 仔细来说，窗口的条件只和当前连续段有关。一旦破坏即重置，前面的窗口作废，而不需要用while逐步收缩。

下图体现了重置的过程：

• 
  1 是初始状态；
  2 遇到了破坏条件；
  3 left移动到right，right重新开始滑动，建立新窗口。

模板

left=0;right=0;for(;right<n;right++){if()left=right;// 1.不满足条件重置maxRes=max(maxRes,right-left+1)// 2.计算连续长度}

LeetCode 674 最长连续递增序列

Leetcode 674 最长连续递增序列
按照模板思考：
1.寻找不满足条件：当nums[i]>=nums[i+1]，即不满足递增序列
2.考虑边界条件：如果right从1开始，则right <n ，且要向前比较，即比较nums[right]和nums[right-1]；
如果right从0开始，则right < n -1，此时是向后比较，即比较 nums[right] 和 nums[right+1]；

// 方式1：和前面比（推荐）for(inti=1;i<n;i++){if(nums[i]>nums[i-1]){...}}// 方式2：和后面比for(inti=0;i<n-1;i++){if(nums[i+1]>nums[i]){...}}

3.更新连续长度

LeetCode 1446 连续字符

Leetcode 1446 连续字符
同上，寻找破坏条件，即s[right] != s[right-1]，注意边界问题。

LeetCode 485 最大连续1的个数

Leetcode 485 最大连续1的个数
简单做的话，是可以用cnt来统计连续1的个数的。
因为本文旨在练习同类题目，于是给出模板写法：

classSolution{public:intfindMaxConsecutiveOnes(vector<int>&nums){intleft=0;intright=0;intcnt=0;intmaxCnt=0;for(;right<nums.size();right++){if(right>0&&nums[right]!=nums[right-1])// 向前比较{left=right;}cnt=right-left+1;maxCnt=max(cnt,maxCnt);}returnmaxCnt;}};

注意一定要if判断条件里一定要写 right > 0。