[LeetCode] 1004. Max Consecutive Ones III

問題

https://leetcode.com/problems/max-consecutive-ones-iii/description/

解答と解説

class Solution:
    def longestOnes(self, nums: List[int], k: int) -> int:
        res = left = count = 0
        for right in range(len(nums)):
            # window内の0の数をカウント
            if nums[right] == 0:
                count += 1
            
            # 0の数がしきい値を超えたらwindowを狭める
            while count > k:
                if nums[left] == 0:
                    count -= 1
                left += 1
            
            # 最大長の比較
            res = max(res, right - left + 1)
        
        return res

numsの配列の要素数をnとした時、

• Time Complexity: O(n)
• Space Complexity: O(1)

可変長のSliding Windowの典型パターン。

どのindexの0をフリップするかを考えるのではなく、「window内に0がk個ある場合に最大長はどうなるか」と言い換えて考えるとわかりやすい。