Leetcode刷题解析——最大连续1的个数

1. 题目链接：1004. 最大连续1的个数 III

2. 题目描述：

给定一个二进制数组 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。
1
2
3
4

示例 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
2
3
4

提示：

• 1 <= nums.length <= 105
• nums[i] 不是 0 就是 1
• 0 <= k <= nums.length

3. 解法（滑动窗口）

3.1 算法思路：

求数组中一段最长的连续区间，要求这段区间内0的个数不要超过k个

3.2 算法流程：

当right小于数组大小的时候，一直循环下列操作：

1. 让当前元素进入窗口，统计0的个数
2. 检查0的个数是否大于k：如果大于k，依次让左侧元素滑出窗口，更新统计的值，直到0的个数恢复正常，
3. 更新结果
4. 循环结束，返回最终结果ret

3.2 C++算法代码：

class Solution {
public:
    int longestOnes(vector& nums, int k) 
    {
        int n=nums.size();
        int ret=0;
        int left=0,right=0;
         int CountZero=0;//统计0出现的次数
        while(rightk)
            {
             //出窗口
                if(nums[left++]==0)
                CountZero--;
            }
            //更新结果
            ret=max(ret,right-left+1);
             right++;
        }
        return ret;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26