一.题目描述
最大连续1的个数
这道题要我们找最大连续1的个数，看到“连续”二字，我们要想到滑动窗口的方法。滑动窗口的研究对象是一个连续的区间，这个区间需要满足某个条件。那么本题要找的是怎样的区间呢？是一个通过翻转0后得到连续1的区间，而最多可以翻转k个字符。
故要找的是包含0的个数不超过k的区间，因为如果超过k个0，即使经过翻转，该区间的1也还是不连续。
题意转化过来后，本题便不再困难。
二.思路分析
滑动窗口是在暴力解法的基础上优化过来的。本题的暴力解法就是两层for循环枚举所有的区间，找出满足条件的区间，通过比较得到最长的区间长度，结果就是数组中连续1的最大个数。
class Solution {
public:
int longestOnes(vector<int>& nums, int k)
{
int n = nums.size();
int ret = 0;
for (int left = 0; left < n; left++)
{
int zero = 0;//记录0的个数
for (int right = left; right < n; right++)
{
if (nums[right] == 0)
{
zero++;
}
//如果0的个数已经超过k,right向后枚举的区间肯定也不符合要求
if (zero > k)
{
break;
}
ret = max(ret, right - left + 1);
}
}
return ret;
}
};要想用滑动窗口，首先要证明right没有回退的必要
如图，right从left位置出发，依次向后枚举，到图中的位置[left, right]区间内0的个数大于k,停了下来。这说明[left, right - 1]区间是满足要求的。
按照暴力枚举策略，left向右移动一步，right回退到left位置。但最终right还是会回到原来的标记处。因为通过上一轮枚举，我们可知图中大括号标记的区间都是符合条件的，而right只有在区间不满足要求时才会停下。所以right没有必要回退，留在原地即可。
那么此时[left, right]区间是否符合条件呢？答案是不一定。因为可能left跳过的是一个1, 0的数量并没有减少，也有可能跳过了一个0，区间内刚好有k个0。
当区间符合条件时，我们让right继续向后移动，接下来的步骤就和上面一样了。当区间不符合条件时，right向后枚举的区间就更不满足了，所以我们让left继续向右移动，直到区间满足要求为止。
故判断应该是一个循环语句，不能简单地只判断一次。
三.代码编写
按照滑动窗口的模版，找到各个条件即可。当枚举的情况满足要求时应该更新结果。什么时候满足要求呢？
1.进窗口之后，zero>=k,符合要求
2.进窗口之后，zero<k,经过若干次出窗口操作后，zero=k ，满足要求
故更新结果应放在整个循环的最后面文章来源：https://www.toymoban.com/news/detail-676832.html
class Solution {
public:
int longestOnes(vector<int>& nums, int k) {
int n =nums.size();
int zero = 0;//记录窗口内0的个数
int left = 0, right = 0;
int ret = 0;
while (right < n)
{
//进窗口
if (nums[right] == 0)
{
zero++;
}
//判断
while (zero > k)
{
//出窗口
if (nums[left] == 0)
{
zero--;
}
left++;
}
//更新结果
ret = max(ret, right - left + 1);
right++;
}
return ret;
}
};时间复杂度O(n)，相比于暴力枚举的O(n^2)提升了不少。文章来源地址https://www.toymoban.com/news/detail-676832.html
到了这里，关于【滑动窗口】leetcode1004：最大连续1的个数的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
