给定一个二进制数组 nums 和一个整数 k,如果可以翻转最多 k 个 0 ,则返回 数组中连续 1 的最大个数 。
示例 1:
输入:nums = [1,1,1,0,0,0,1,1,1,1,0], K = 2
输出:6
解释:[1,1,1,0,0,1,1,1,1,1,1]
粗体数字从 0 翻转到 1,最长的子数组长度为 6。示例 2:
输入:nums = [0,0,1,1,0,0,1,1,1,0,1,1,0,0,0,1,1,1,1], K = 3
输出:10
解释:[0,0,1,1,1,1,1,1,1,1,1,1,0,0,0,1,1,1,1]
粗体数字从 0 翻转到 1,最长的子数组长度为 10。提示:
1 <= nums.length <= 105nums[i]不是0就是10 <= k <= nums.length
解题思路 -- 滑动窗口
首先这道题如果我们直接去做翻转零的话,那么其实会比较复杂,因为我们枚举完一个结果之后,在枚举其它结果集的时候,就要将原来的零翻转回来,这实现起来还是比较复杂的,所以我们需要转变一下思路!
因为题目说最多翻转 k 个零,那么也就是说,一个区间内,最多零的个数就不能超过 k 个,那么我们只需要看看哪段不超过 k 个零的区间中最长的那个区间,不就是我们要求的最大连续 1 的区间吗,也就相当于,直接把零看作 1,就不需要去翻转了!
那这道题就可以用双指针的 ”滑动窗口“ 来解决了,无非就是比之前要多做点细节,什么细节呢❓❓❓
我们需要用一个变量 zero 来记录当前窗口内零的个数,根据零的个数来判断什么时候出窗口,什么时候进窗口!
并且,最好先理解暴力破解对这道题的思路,因为 ”滑动窗口“ 就是基于暴力破解优化的,这里因为前两道题我们都讲过暴力破解的思路啦,就是简单的枚举所有的情况,这里就不再赘述了!
算法步骤如下所示:
- 定义窗口指针
left = 0,right = 0,并且定义一个变量zero用于记录窗口的零的个数,定义一个maxlen记录窗口的最大长度right开始往后遍历,让元素进窗口
- 如果
nums[right] == 1,则不需要处理- 如果
nums[right] == 0,此时要让zero++,并且判断zero是否大于k个,是的话则让left++,直到left遇到了零,并让这个零出窗口为止!- 更新最大长度
- 重复上述操作直到
right出界!
class Solution {
public:
int longestOnes(vector<int>& nums, int k) {
int left = 0; // 窗口左边界指针
int zero = 0; // 窗口中0的个数
int maxlen = 0; // 最大长度
for(int right = 0; right < nums.size(); ++right)
{
if(nums[right] == 0)
{
zero++; // 进窗口
while(zero > k)
{
if(nums[left] == 0) // 出窗口
zero--;
left++;
}
}
maxlen = max(maxlen, right - left + 1); // 更新结果
}
return maxlen;
}
};