本篇文章讲的是“最大连续1的个数”这道题，从最开始的简单暴力到用滑动窗口算法实现解题的思路历程，有需要借鉴即可。
1.题目
题目链接：LINK
2.暴力求解
题目解析：这里看到题目之后，大概就是让我们找在这穿数字中连续的1最大有几个，但是这个题目还有个“翻转”的设定。
暴力求解：其实我们想到的暴力求解无非是挨个遍历，定义两个指针，一个是start指针，一个是end指针，start首先指向第一个数字，end也指向第一个数字，碰到0我们就“反转一下”，直到反转次数不足或者说是该数组遍历完成。这样的话我们可以继续start指向下一个数字，重复上述过程，期间取最大值即可。
技巧(反转转换)：题目中所说的“反转”，可是我们如果真的反转了，在下一次遍历时候还得改回来，很麻烦，这里可以用个变量统计一下遇到0的个数就行，不用真的进行“翻转”。
大概是下面这个过程：
时间复杂度：O(N^2)
代码我写好了，除了时间复杂度问题之外，没什么问题哈。
class Solution {
public:
//暴力解法
int longestOnes(vector<int>& nums, int k) {
int zero = 0;
int n = nums.size();
int ret = 0;
for(int left = 0;left < n;left++)
{
zero = 0;
int right = left;
while(right < n)
{
if(nums[right] == 1)
{
right++;
}
else
{
zero++;
if(zero > k)
break;
right++;
}
}
ret = max(ret,right - left);
}
return ret;
}
};
时间复杂度比较高哈，虽然说这种方法很挫，但也是一种方法…我们下面在暴力求解的基础上对该题目进行优化：
3.滑动窗口解法
一上来，不可能一下就可以想到滑动窗口的。这里我必须强调一下：这里滑动窗口的解法是在暴力求解的基础上不断优化，在优化的过程中发现满足滑动窗口的规律，因而说最终优化成了滑动窗口算法。
3.1优化一：end重返start优化，end指针不回退
首先，我再看这个暴力解法的过程中，我们把不同的start位置看成不同的”组“，在不同组的时候，命名end可以继续向右移动，但是end到下一个start的时候又回到了start位置，显然十分消耗性能，因而这个地方可以优化一下。
比如说：
3.2优化二：某一start指向下，一定不是最大的时候，直接优化掉
这个优化什么意思呢？比如下图：第二组铁定比第一组短，压根就没必要去走第二组的情况
也就是说，第一组遍历完了，直接进行下图所示的这组，干脆直接这样：
然后到这里，两个指针，都是同向的，且不回退，这时候我就想到这是典型的”滑动窗口“题目，所以可以直接优化成滑动窗口解法：
class Solution {
public:
//暴力解法
int longestOnes(vector<int>& nums, int k) {
int zero = 0;
int n = nums.size();
int ret = 0;
int left = 0,right = 0;
for(right = 0;right < n ;right++)
{
//进窗口
if(nums[right] == 0)
{
zero++;
}
//出窗口之后也会满足条件
while(zero > k)
{
if(nums[left++] == 0)
{
zero--;
}
}
//每次进窗口满足条件的情况下会自动更新，出完窗口下也会自动更新
ret = max(ret,right - left + 1);
}
return ret;
}
};
EOF
