動機
基本款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 either0
or1
.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