Max Consecutive Ones III

Given an arrayA of 0s and 1s, we may change up toK values from 0 to 1.

Return the length of the longest (contiguous) subarray that contains only 1s.

Example 1:

Input: A = [1,1,1,0,0,0,1,1,1,1,0], K = 2
Output: 6
Explanation: 
[1,1,1,0,0,1,1,1,1,1,1]
Bolded numbers were flipped from 0 to 1.  The longest subarray is underlined.

Example 2:

Input: A = [0,0,1,1,0,0,1,1,1,0,1,1,0,0,0,1,1,1,1], K = 3
Output: 10
Explanation: 
[0,0,1,1,1,1,1,1,1,1,1,1,0,0,0,1,1,1,1]
Bolded numbers were flipped from 0 to 1.  The longest subarray is underlined.

Note:

1 <= A.length <= 20000
0 <= K <= A.length
A[i] is 0 or 1

分析

也是Map，while/if count(0) >k 就缩头，出来就是count(0)<=k，符合题目的up toK

class Solution:
    def longestOnes(self, A: List[int], K: int) -> int:
        l = r = res = cnt = 0
        ll = len(A)
        while r < ll:
            if A[r] == 0:
                cnt += 1
            r += 1    
            if cnt > K:#while也行 慢
                if A[l] == 0:
                    cnt -=1
                l += 1
            res = max(res, r-l)
        return res