本篇文章讲的是“最大连续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