最大连续1的个数3

1004. 最大连续1的个数 III

难度中等181收藏分享切换为英文接收动态反馈

给定一个由若干 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。

提示：

1. 1 <= A.length <= 20000
2. 0 <= K <= A.length
3. A[i] 为 0 或 1

滑动窗口

使用滑动窗口维护窗口中1的数量，如果窗口中0的数量 大于 窗口长度减去（1的数量+K的数量），说明窗口不满足条件

找到一个平衡，即：左指针对应的前缀和+k等于右指针对应的前缀和，此时可以满足题意条件，否则不能满足题意条件，需要右移左指针

class Solution {
    public int longestOnes(int[] A, int K) {
        int n=A.length;
        // 左右边界
        int l=0,r=0;
        int max=0;
        int oneCount=0;
        while(r<n){
            oneCount+=A[r];
            // 边界条件
            while(r-l+1>K+oneCount&&l<r){
                oneCount-=A[l];
                l++;
            }
            // 边界条件r==l时需要处理
            max=r>l?Math.max(r-l+1,max):max;
            r++;
        }
        return max;
    }
}

二分查找

class Solution {
    public int longestOnes(int[] nums, int k) {
        int n =nums.length;
        int [] preSum = new int[n+1];

        for(int i=1;i<=n;i++){
            preSum[i] = preSum[i-1]+(1-nums[i-1]);
        }

        int ans = 0;
        for(int right=0;right<n;right++){
            // 区间中,前缀和的0的数量
            int leftZero =preSum[right+1]-k;
            int left = binSearch(preSum,leftZero);
            ans = Math.max(right-left+1,ans);
        }
        return ans;
    }

    
    public int binSearch(int []preSum,int target){
        int l = 0, r = preSum.length-1;
        while(l<r){
            int m = l+(r-l)/2;
            if(preSum[m] < target){
                l = m + 1;
            }else{
                // 注意这里,是不满足条件就移动左指针,而不是优先移动右指针
                r = m;
            }
        }
        return l;
    }
}

赏

谢谢你请我吃糖果

微信