[LeetCode] 487. Max Consecutive Ones II

487. Max Consecutive Ones II

Medium

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

 

Example 1:

Input: nums = [1,0,1,1,0]
Output: 4
Explanation: 
- If we flip the first zero, nums becomes [1,1,1,1,0] and we have 4 consecutive ones.
- If we flip the second zero, nums becomes [1,0,1,1,1] and we have 3 consecutive ones.
The max number of consecutive ones is 4.

Example 2:

Input: nums = [1,0,1,1,0,1]
Output: 4
Explanation: 
- If we flip the first zero, nums becomes [1,1,1,1,0,1] and we have 4 consecutive ones.
- If we flip the second zero, nums becomes [1,0,1,1,1,1] and we have 4 consecutive ones.
The max number of consecutive ones is 4.

 

Constraints:

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

 

Follow up: What if the input numbers come in one by one as an infinite stream? In other words, you can't store all numbers coming from the stream as it's too large to hold in memory. Could you solve it efficiently?

---

문제 풀이

• 주어진 배열에 1과 0만 있다. 
• 여기서 하나의 0을 1로 바꿨을때 연속으로 1이 가장 길게 있을 수 있는 답을 구해라.
• 제한 사항을 보면 배열의 최대 길이가 10^5이기 때문에 O(N) 혹은 O(NlogN)의 풀이 방법을 찾아야한다.
• 슬라이딩 윈도우를 사용하여 문제를 풀어야한다.
• 우선 두개의 포인터를 두고 0의 개수를 저장할 수 있는 변수를 저장한다.
• 오른쪽 포인터를 배열의 마지막까지 이동시키면서 만약 0이 발견되면 0의 개수를 늘려준다. 
• 0이 한개거나 없다면 오른쪽 포인터에서 왼쪽 포인터를 빼고 +1 을 하여 최대값을 구한다.
• 만일 0의 개수가 2개라면 왼쪽 포인터를 증가시켜 0이 나올때까지 이동시키고, 왼쪽 포인터부터 오른쪽 포인터 사이의 0 개수를 줄여준다.

소스 코드

#Sliding Window
class Solution:
    def findMaxConsecutiveOnes(self, nums: List[int]) -> int:
        total, l, r, zero = 0, 0, 0, 0
        while r < len(nums):
            if nums[r] == 0:
                zero += 1
            while zero == 2:
                if nums[l] == 0:
                    zero -= 1
                l += 1
            total = max(total, r - l + 1)
            r += 1
        return total