1004. Max Consecutive Ones III

[fockspaces]

sliding window

1. window 對 '0' 最大容忍總數為 k
2. 訂 length, 每次迭代都 + 1
3. 過程中遇到 0 則消掉 quota_zeros
4. 如果 quota 用完，需要開始限縮 window 長度後再結算總長

class Solution:
    def longestOnes(self, nums: List[int], k: int) -> int:
        quota_for_zeros = k
        max_ones = length = 0
        for i in range(len(nums)):
            if nums[i] == 0:
                quota_for_zeros -= 1
                length += 1
            else:
                length += 1

            while quota_for_zeros < 0 and length > 0:
                if nums[i - length + 1] == 0:
                    quota_for_zeros += 1
                length -= 1
            max_ones = max(max_ones, length)
        return max_ones

[fockspaces]

GPT imrprove:

1. 用雙指針會更直覺
2. 不需要 check length > 0，當 left == right 時，quota_for_zeros 必然 >= 0
3. 命名改進

class Solution:
    def longestOnes(self, nums: List[int], k: int) -> int:
        left = zero_counts = max_ones = 0
        for right in range(len(nums)):
            if nums[right] == 0:
                zero_counts += 1
            while zero_counts > k:
                if nums[left] == 0:
                    zero_counts -= 1
                left += 1
            max_ones = max(max_ones, right - left + 1)
        return max_ones