leetcode 1004. 最大连续1的个数 III | 中等难度

1. 题目详情

给定一个二进制数组 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 <= 105
nums[i] 不是 0 就是 1
0 <= k <= nums.length

1. 原题链接

leetcode 1004. 最大连续1的个数 III

2. 基础框架

● Cpp代码框架

class Solution {
public:
    int longestOnes(vector<int>& nums, int k) {

    }
};

2. 解题思路

1. 题目分析

$(1)$ 本题给出二进制数组nums（只包含0/1），允许最多翻转k个0，找出最长连续且全1的子数组。

$(2)$ 首先如果什么都不想，直接按照题意进行翻转0操作并枚举全1连续子数组，翻转完一个位置的0后还要还原回去，总的来说这是一件非常麻烦的事。

$(3)$ 对于暴力枚举，我们也不是直接翻转0再枚举的；而是模拟（计数）翻转，定义一个0计数器zeroCnt，记录已翻转0的次数（即遇到0不翻转而是计数器zeroCnt自增1表示进行了翻转）。

这时进行暴力枚举操作就十分容易了：
定位起始位置left，枚举以left为起始位置，right为结束位置的所有满足题意的子数组。

如果right位置的新元素是1，则满足题意，right++；
如果right位置的新元素是0，0计数器自增1(zeroCnt++)，之后分两种情况：
————1. 如果zeroCnt<= k，说明此时可以把0当做1使用，满足题意，right++；
————2. 如果zeroCnt > k，说明此时不可以把0当做1使用，即不满足题意，以left为起始位置的最长连续全1子数组只能到right-1位置，right及其之后的位置上的元素都不符合题意，此时就可以枚举以left+1为起始位置的所有子数组了。

2. 算法原理

$(1)$ 滑动窗口：对暴力枚举思路的优化

$(2)$ 通过对上述暴力枚举的分析，以left为起始位置，right为结束位置的枚举过程，每次不满足题意时，left都右移1位，right回退到left位置继续枚举子数组。

$(3)$ 这其中right回退的操作，导致了重复的枚举操作：
在上一次枚举过程的最后一次结果中，满足题意的范围是[left, right-1]，所以本次right指针回退并继续从left+1开始枚举操作，那么[left+1, right-1]已经有效范围会被right指针重新枚举。

$(4)$ 优化：很明显[left+1,right-1]是符合题意的子数组，所以对于right不必回退，只需要left右移，直到zeroCnt<=k（即[left, right]是连续全1子数组）即可。

$(5)$ 思路：

1. 初始化left=0，right=0，maxlen=0
2. 进窗口：如果nums[right]是0，则zeroCnt++；否则什么也不做
3. 循环判断：如果zeroCnt>k，即不满足题意：
4. 出窗口：left右移，直到0计数器不大于k
5. 更新结果：maxlen = max(maxlen, right-left+1)

3. 时间复杂度

暴力枚举 $O(n^2)$

滑动窗口 $O(n)$

left和right同向移动，直到末尾，即遍历一遍数组nums。

3. 代码实现

class Solution {
public:
    int longestOnes(vector<int>& nums, int k) {
        int maxlen = 0;
        int zeroCnt = 0;
        int l = 0, r = 0;
        int n = nums.size();
        while(r < n){
            if(nums[r] == 0) zeroCnt++;//进窗口
            while(zeroCnt > k){//判断
                if(nums[l++] == 0) zeroCnt--;//"滚出"窗口
            }
            maxlen = max(maxlen, r - l + 1);//更新结果
            r++;//下一次进窗口做准备
        }
        return ret;
    }
};

4. 知识与收获

$(1)$ 翻转0操作按照题意直接写会非常麻烦，所以设置了0计数器来记录翻转0的数量，而不是真正的翻转操作，这是第一步优化的方法，为滑动窗口算法的介绍铺路。

---

$The$ $End$