[LeetCode] 487. Max Consecutive Ones II

[grandyang]

 

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:

• The input array will only contain 0 and 1.
• 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?

 

这道题在之前那道题 Max Consecutive Ones 的基础上加了一个条件，说有一次将0翻转成1的机会，问此时最大连续1的个数，再看看 follow up 中的说明，很明显只遍历一次数组，那我们想，肯定需要用一个变量 cnt 来记录连续1的个数吧，那么当遇到了0的时候怎么处理呢，因为有一次0变1的机会，所以遇到0了还是要累加 cnt，然后此时需要用另外一个变量 cur 来保存当前 cnt 的值，然后 cnt 重置为0，以便于让 cnt 一直用来统计纯连续1的个数，然后我们每次都用用 cnt+cur 来更新结果 res，参见代码如下：

 

解法一：

class Solution {
public:
    int findMaxConsecutiveOnes(vector<int>& nums) {
        int res = 0, cur = 0, cnt = 0;
        for (int num : nums) {
            ++cnt;
            if (num == 0) {
                cur = cnt;
                cnt = 0;
            } 
            res = max(res, cnt + cur);
        }
        return res;
    }
};

 

上面的方法有局限性，如果题目中说能翻转k次怎么办呢，最好用一个通解来处理这类问题。可以维护一个窗口 [left,right] 来容纳至少k个0。当遇到了0，就累加 zero 的个数，然后判断如果此时0的个数大于k，则右移左边界left，如果移除掉的 nums[left] 为0，那么 zero 自减1。如果不大于k，则用窗口中数字的个数来更新 res，参见代码如下：

 

解法二：

class Solution {
public:
    int findMaxConsecutiveOnes(vector<int>& nums) {
        int res = 0, zero = 0, left = 0, k = 1;
        for (int right = 0; right < nums.size(); ++right) {
            if (nums[right] == 0) ++zero;
            while (zero > k) {
                if (nums[left++] == 0) --zero;
            }
            res = max(res, right - left + 1);
        }
        return res;
    }
};

 

上面那种方法对于 follow up 中的情况无法使用，因为 nums[left] 需要访问之前的数字。我们可以将遇到的0的位置全都保存下来，这样需要移动 left 的时候就知道移到哪里了：

 

解法三：

class Solution {
public:
    int findMaxConsecutiveOnes(vector<int>& nums) {
        int res = 0, left = 0, k = 1;
        queue<int> q;
        for (int right = 0; right < nums.size(); ++right) {
            if (nums[right] == 0) q.push(right);
            if (q.size() > k) {
                left = q.front() + 1; q.pop();
            }
            res = max(res, right - left + 1);
        }
        return res;
    }
};

 

Github 同步地址：

#487

 

类似题目：

Max Consecutive Ones

Max Consecutive Ones III

 

参考资料：

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

https://discuss.leetcode.com/topic/75439/java-concise-o-n-time-o-1-space

https://discuss.leetcode.com/topic/75445/java-clean-solution-easily-extensible-to-flipping-k-zero-and-follow-up-handled

 

LeetCode All in One 题目讲解汇总(持续更新中...)