Leetcode # 1004. Max Consecutive Ones III

Problem

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

相關例題

• Leetcode # 485. Max Consecutive Ones

Solution: Sliding Window

Time Complexity: O(len(nums))
Space Complexity: O(1)
(The input and output generally do not count towards the space complexity.)

class Solution:
  def longestOnes(self, nums: List[int], k: int) -> int:
    ans = left  = flipped = 0
    for right in range(len(nums)):
      # do logic here to add arr[right] to curr
      if nums[right] == 0: flipped += 1

      while left <= right and flipped > k:
        # remove arr[left] from curr
        if nums[left] == 0: flipped -= 1
        left += 1

      # update ans
      ans = max(ans, right - left + 1)
    
    return ans

Another Sliding Window Solution

Time Complexity: O(len(nums))
Space Complexity: O(1)
(The input and output generally do not count towards the space complexity.)

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

      if flipped > k:
        if nums[left] == 0: flipped -= 1
        left += 1
    
    return right - left + 1

備註

Solution 1 的while left <= right and flipped > k
會把 sliding window 調整至 flipped 個數 <= k

此處的if flipped > k第一次觸發的時候
nums[right] 必為 0

1. nums[left] == 0:
   ⇒ 削減 flipped
2. nums[left] == 1:
   right - left + 1就會是flipped在至今為止合格範圍內的最大長度

Last Updated on 2023/08/29 by A1go