题目描述

给定一个由若干 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 <= A.length <= 20000
0 <= K <= A.length
A[i] 为 0 或 1 

算法1

(动态规划) $O(n)$

用cnt_0[i]来表示数组A中前i个数中有多少个0，那么我们要求得的就是另满足cnt_0[i] - cnt_0[j] <= K的i - j最大。一种直接暴力的做法就是，遍历i和j，判断是否满足条件并更新最大值，但这种做法的时间复杂度为$O(n^2)$，会超时。我们观察到，如果对于i和j，若cnt_0[i] - cnt_0[j] > K，那么更小的j值肯定也不满足条件，所以在遍历的时候，只要维护一个递增的指针，不满足条件就增加即可，不用从头遍历。

时间复杂度分析：双指针，每个cnt_0[i]至多被遍历2次，所以时间复杂度为$O(n)$

Python3 代码

class Solution:
    def longestOnes(self, A: List[int], K: int) -> int:
        l = len(A)
        cnt_0 = [0 for _ in range(l + 1)]
        ans = 0
        j = 0
        for i in range(l):
            if A[i] == 0:
                cnt_0[i + 1] = cnt_0[i] + 1
                while cnt_0[i + 1] - cnt_0[j] > K:
                    j += 1
            else:
                cnt_0[i + 1] = cnt_0[i]
            ans = max(ans, i - j + 1)

        return ans