2021年2月19日 Leetcode每日一题：1004. 最大连续1的个数 III

最大连续1的个数Ⅲ

1.题目描述

给定一个由若干 0 和 1 组成的数组 A，我们最多可以将 K 个值从 0 变成 1 。

返回仅包含 1 的最长（连续）子数组的长度。

2.示例

示例 1：

输入：A = [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：

输入：A = [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。

3.读题

这一题题意简单明了。数组由数字1和0组成，我们可以将其中任意K个0变成1。我们要找出，将数组中的K个0变成1之后，可以在数组中组成的最长的由连续的1组成的子数组的长度。

4.思路

其实，将K个0转换为1之后，连续的1组成的子数组长度为最长，这个问题可以转换为：

• 在数组中取一个子数组，其中的0的个数最多为K个，怎样将这个子数组取得最长。

由于涉及到了0的个数最多为K个这样的问题，因此这一题肯定可以用滑动窗口的方法来做。

将窗口的左端点先设定为0，右端点从0开始往右滑动，根据右端点的值以及窗口内0的个数，在右端点滑动的过程中可能有三种情况：

1.右端点处的值为1，此时只需要将右端点继续往右滑动即可。
2.右端点处的值为0且窗口内0的个数小于K个，此时将窗口右端点往右滑动，窗口内0的个数加1。
3.右端点处的值为0且窗口内的0的个数等于K个，此时先将目前窗口的长度的值减一（因为右端点多出了一个0）作为满足题意的子数组长度的极大值来更新最大值，然后左端点向右滑动直到将原有的一个0滑出窗口。

最后，由于存在某次滑动后窗口内的0的个数始终小于等于K直到数组结束这种情况，因此在滑动结束后还需要将当前窗口的长度作为一个极大值，去更新整体的最大值。

4.代码

class Solution {
    public int longestOnes(int[] A, int K) {
        int left = 0;
        int count = 0;
        int max = 0;
        for(int r=0;r<A.length;r++){
            if(A[r]==1){
                continue;
            }else if(A[r]==0&&count<K){
                count++;
            }else{
                max = Math.max(max,(r-left));
                while(A[left]!=0) left++;
                left++;
            }
        }
        max = Math.max(max,(A.length-left));
        return max;
    }
}