【力扣每日一题：2-19】1004. 最大连续1的个数 III【中等】

清疚 2022-10-30 13:26 141阅读 0赞

## 题目链接 ##

[1004. 最大连续1的个数 III【中等】][1004. _1_ III]

## 题目简介 ##

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

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

示例 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。

## 题目解析 ##

*  我们可以将K个值为0的转成K个值为1的，求一个连续数组，里面`包含的1是最多的`
 *  我们可以使用滑动窗口进行解决
    
     *  我们定义 *left* 和 *right* 分别代表滑动窗口的两端
     *  *right* 主动右移：*right* 指针每次移动一步。当 A\[right\] 为 0，说明滑动窗口内增加了一个 0；
     *  *left* 主动右移：判断此时窗口内 0 的个数，如果超过了 K，则 *left* 指针被迫右移，直至窗口内的 0 的个数小于等于 K 为止。
     *  每次都求出 max，返回即可

## 题目代码 ##

class Solution {
        
        public int longestOnes(int[] A, int K) {
        
            int len = A.length;
            int left = 0;
            int right = 0;
            int res = 0;
            int sum = 0;
    
            while(right < len){
        
                // 记录当前滑动窗口内含有多少0
                if(A[right] == 0){
        
                    sum++;
                }
    
                right++;
                // 如果当前滑动窗口中的 0 超过 K 个，则需要考虑 left 的坐标
                
                while(sum > K){
        
                    // 如果下一个为 0 的话,则区间内需要去除一个 0 
                    if(A[left] == 0){
        
                        sum--;
                    }
                    left++;
                }
    
                res = Math.max(res, right - left);
            }
            
            return res;
        }
    }

[1004. _1_ III]: https://leetcode-cn.com/problems/max-consecutive-ones-iii/