487. Max Consecutive Ones II

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. 初始化两个指针left和right，用于标记窗口的左右边界，以及一个变量zeros来记录窗口中0的数量。
2. 移动right指针扩展窗口，如果遇到0，则zeros增加。
3. 当窗口内的0的数量超过1时，移动left指针以缩小窗口，直到窗口内再次只有一个0或没有0。
4. 在每一步中，如果窗口内的0的数量不超过1，更新最大长度。

**时间复杂度：**O(n)，其中n是数组的长度，因为每个元素只被访问一次。

**空间复杂度：**O(1)，只使用了固定的额外空间。

Problem Analysis: This problem asks us to find the maximum length of consecutive 1s that can be achieved by flipping at most one 0. This is a classic sliding window problem, also involving array traversal.

Solution Approach:

1. Initialize two pointers, left and right, to mark the boundaries of the window, and a variable zeros to count the number of zeros within the window.
2. Move the right pointer to expand the window, increase zeros if encountering a 0.
3. When the number of zeros within the window exceeds one, move the left pointer to reduce the window until there is only one or no zero within it again.
4. At each step, if the number of zeros within the window does not exceed one, update the maximum length.

Time Complexity: O(n), where n is the length of the array, as each element is visited only once.

Space Complexity: O(1), as only a fixed amount of extra space is used.

function findMaxConsecutiveOnes(nums: number[]): number {
if (nums.length === 1) return 1;
let left = 0, right = 0, zeros = 0;
let max = 0;
for (; right < nums.length; right++) {
if (nums[right] === 0) {
zeros++;
}
if (zeros <= 1) { // valid, continue
max = Math.max(max, right - left + 1);
} else {
// Move left until it escapse a 0
while (nums[left] !== 0) {
left++;
}
left++;
zeros--;
}
}
return max;
};

This site uses Akismet to reduce spam. Learn how your comment data is processed.