487. Max Consecutive Ones II 最大连续1的个数 II

题目地址：https://leetcode-cn.com/problems/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、 Theinputarraywillonlycontain0and1.；
2、 Thelengthofinputarrayisapositiveintegerandwillnotexceed10,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?

题目大意

最多可以把数组中的一个0翻转成1，求能够成的最长连续1有多少。

解题方法

动态规划

我第一遍做这个题的时候，使用的是从左向右和从右向左两次遍历，找出每个0的左右两部分连续1的个数相加。这样也能过，但是有点麻烦。

比较好的解决方案是动态规划，定义两个变量left, right。

1、 left的含义是：遇到了0，并翻转了该0时，包含该0的位置和其左侧连续的1的的长度；
2、 right的含义是：从上次遇到0之后，累加得到的连续1的个数；

举例说明：

维护两个变量：

1、 当遇到1时，用right保存已经遇到的连续的1（不含翻转0得到的1）；
2、 当遇到0时，把这个0翻转，更新left为right+1（把位置的0翻转为1），更新right为0；

left+right的最大值即为所求。

C++代码如下：

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

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19

参考资料：https://www.cnblogs.com/grandyang/p/6376115.html

2022

DDKK.COM 弟弟快看-教程，程序员编程资料站，版权归原作者所有

本文经作者：负雪明烛 授权发布，任何组织或个人未经作者授权不得转发