题目来源:力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台
本期讲解滑动窗口经典例题,我会从三个点开始讲解题目1.题目解析2.算法原理 3.编写代码
1.题目解析
这道题目理解起来还是比较简单的,我们简单分析一下,也就是给定一个数组,数组是由1和0组成的,给定了你一个条件,可以"翻转"最多k个0到1,然后让你计算数组中的连续1的最大个数
示例
2.算法详解
这个题目最令人懊恼的就是翻转0这个操作,如果说我们真的去题目中将0改成1的话,代码的复杂量将会上升,极其不好写,所以说我们需要对翻转这个操作进行修改,优化,
题目给定了一个k值,要求翻转的0不能超过k,也就是说我们只需要让寻找的这个区间的0的个数不超过k即可,只要不超过k就说明这个区间的0是一定能够成功翻转成1的,也就不需要真正的进行翻转0的操作了
到此处,我们其实已经可以进行暴力枚举操作了
在枚举的过程中,我们先固定左边的值,再依次枚举所有的可能,可是,在这里我们发现了一个规律,右边的值在每次枚举的时候似乎进行了不必要的操作,每次都要从左边重新开始走,
优化成滑动窗口:
在这里我们用count计算0的个数
我们先让right先走,用right判断,当走到right=0的时候,让count++,当count=3的时候,也就是count>k的时候,这里就算出来一个区间了,也就是right-left+1,进行接下来的操作,如果这里是暴力解法的话,我们只需要将left++然后让right继续进行重复的操作,显然这里浪费了很多时间,
我们可以当count>2的时候,让left走,left走到0的时候,让count--,然后进入count<=k的时候,又让right走判断,直到right走到尾为止
所以现在我们已经发现了两个规律,变成滑动窗口的思想就是如下
3.编写代码
class Solution {
public:
int longestOnes(vector<int>& nums, int k) {
int n=nums.size();
int len=0;
int zero=0;
for(int left=0,right=0;right<n;right++)
{
if(nums[right]==0)
++zero;
while(zero>k)
{
if(nums[left]==0){
--zero;
}
++left;
}
len=max(len,right-left+1);
}
return len;
}
};
