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

算法入门一滑动窗口之允许重置的窗口允许重置的窗口模板LeetCode 674 最长连续递增序列LeetCode 1446 连续字符LeetCode 485 最大连续1的个数允许重置的窗口例如 Leetcode 485 / 1446 / 674 这类题目其本质是可变窗口。条件一旦被破坏左指针直接跳到右指针位置不逐步收缩仔细来说窗口的条件只和当前连续段有关。一旦破坏即重置前面的窗口作废而不需要用while逐步收缩。下图体现了重置的过程1 是初始状态2 遇到了破坏条件3 left移动到rightright重新开始滑动建立新窗口。模板left0;right0;for(;rightn;right){if()leftright;// 1.不满足条件重置maxResmax(maxRes,right-left1)// 2.计算连续长度}LeetCode 674 最长连续递增序列Leetcode 674 最长连续递增序列按照模板思考1.寻找不满足条件当nums[i]nums[i1]即不满足递增序列2.考虑边界条件如果right从1开始则right n 且要向前比较即比较nums[right]和nums[right-1]如果right从0开始则right n -1此时是向后比较即比较 nums[right] 和 nums[right1]// 方式1和前面比推荐for(inti1;in;i){if(nums[i]nums[i-1]){...}}// 方式2和后面比for(inti0;in-1;i){if(nums[i1]nums[i]){...}}3.更新连续长度LeetCode 1446 连续字符Leetcode 1446 连续字符同上寻找破坏条件即s[right] ! s[right-1]注意边界问题。LeetCode 485 最大连续1的个数Leetcode 485 最大连续1的个数简单做的话是可以用cnt来统计连续1的个数的。因为本文旨在练习同类题目于是给出模板写法classSolution{public:intfindMaxConsecutiveOnes(vectorintnums){intleft0;intright0;intcnt0;intmaxCnt0;for(;rightnums.size();right){if(right0nums[right]!nums[right-1])// 向前比较{leftright;}cntright-left1;maxCntmax(cnt,maxCnt);}returnmaxCnt;}};注意一定要if判断条件里一定要写 right 0。