0487：最大连续1的个数 II（★）

力扣第 487 题

题目

给定一个二进制数组 nums ，如果最多可以翻转一个 0 ，则返回数组中连续 1 的最大个数。

示例 1：

输入：nums = [1,0,1,1,0]
输出：4
解释：翻转第一个 0 可以得到最长的连续 1。
当翻转以后，最大连续 1 的个数为 4。

示例 2:

输入：nums = [1,0,1,1,0,1]
输出：4

提示:

• 1 <= nums.length <= 105
• nums[i] 不是 0 就是 1.

进阶：如果输入的数字是作为 无限流 逐个输入如何处理？换句话说，内存不能存储下所有从流中输入的数字。您可以有效地解决吗？

分析

用滑动窗口维护最多包含一个 0 的区间即可。

不过本题要求无限流，考虑用递推的方法：

• 令 dp[i][0] 代表以 i 结尾的最大连续 1 长度，dp[i][1] 代表以 i 结尾的最多包含一个 0 的最大连续长度
• dp[i] 只和 dp[i-1] 的状态有关，可以优化为两个参数

解答

1
2
3
4
5
6

def findMaxConsecutiveOnes(self, nums: List[int]) -> int:
	res, a, b = 0, 0, 0
	for x in nums:
		a, b = (a+1,b+1) if x else (0, a+1)
		res = max(res, b)
	return res

80 ms