目录

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