Max Consecutive Ones II

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

Example 1:

Input: [1,0,1,1,0]
Output: 4
Explanation: Flip the first zero will get the the maximum number of consecutive 1s.
    After flipping, the maximum number of consecutive 1s is 4.

Note:

1. The input array will only contain 0 and 1.
2. The length of input array is a positive integer and will not exceed 10,000

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?

Tips:

Time： O(n)

用2pointers走两遍就可以，left和right，先走right，当0的个数大于两个的时候把left移到第一个0后一位，算出结果，然后接着走。 follow up部分用queue或者arraylist记住每个0的位置即可。

Code:

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

public class Solution {
    public int findMaxConsecutiveOnes(int[] nums) {
        int max = 0, zeros = 0;
        for (int l = 0, r = 0; r < nums.length; r++) {
            if (nums[r] == 0) zeros++;
            while (zeros == 2) {
                while (nums[l] != 0) l++;
                l++;
                zeros--;
            } 
            max = Math.max(max, r - l + 1);
        }
        return max;
    }
}

Follow Up: Time: O(n) Space: O(k)

public int findMaxConsecutiveOnes(int[] nums) {                 
    int max = 0, k = 1; // flip at most k zero
    Queue<Integer> zeroIndex = new LinkedList<>(); 
    for (int l = 0, h = 0; h < nums.length; h++) {
        if (nums[h] == 0)
            zeroIndex.offer(h);
        if (zeroIndex.size() > k)                                   
            l = zeroIndex.poll() + 1;
        max = Math.max(max, h - l + 1);
    }
    return max;                     
}