LeetCode 1004.最长连续1的个数

给定一个由若干 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。
算法：动态规划，双指针

我们用f[i]表示以第i个数字结尾时0的长度，则f[i+1]=f[i]+nums[i]==0。

当0的长度大于k时，我们需要将另一个指针往前移

每次更新两个指针的长度最大值，即为所求

class Solution {
public:
    int longestOnes(vector<int>& A, int K) {
        int n=A.size();
        vector<int> f(n+1,0);
        int res=0,j=0;
        for(int i=0; i<n; i++){
            if(!A[i]){
                f[i+1]=f[i]+1;
                while((f[i+1]-f[j])>K)j++;
            }
            else
                f[i+1]=f[i];
            res=max(res,i-j+1);
        }
        return res;
    }
};

LeetCode 1004.最长连续1的个数

原文：https://www.cnblogs.com/programyang/p/11152839.html