動機

基本款sliding window

Problem

Given a binary array nums and an integer k, return the maximum number of consecutive 1's in the array if you can flip at most k 0's.

 

Example 1:

Input: nums = [1,1,1,0,0,0,1,1,1,1,0], k = 2Output: 6Explanation: [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: nums = [0,0,1,1,0,0,1,1,1,0,1,1,0,0,0,1,1,1,1], k = 3Output: 10Explanation: [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.

 

Constraints:

  • 1 <= nums.length <= 105
  • nums[i] is either 0 or 1.
  • 0 <= k <= nums.length

Sol

class Solution:
    def longestOnes(self, nums: List[int], k: int) -> int:
        i = cnt = ret = 0
        
        for j,n in enumerate(nums):
            if n == 0:
                cnt += 1
            while i <= j and cnt > k:
                if nums[i] == 0:
                    cnt -= 1
                i += 1
            ret = max(ret, j-i+1)
        return ret