487. 最大连续1的个数II

Difficulty
Medium
Tags
动态规划
滑动窗口
URL
Star

题目描述

给定一个二进制数组，你可以最多将 1 个 0 翻转为 1，找出其中最大连续 1 的个数。
示例 1：
输入：[1,0,1,1,0]
输出：4
解释：翻转第一个 0 可以得到最长的连续 1。
当翻转以后，最大连续 1 的个数为 4。
注：
  • 输入数组只包含 0 和 1.
  • 输入数组的长度为正整数，且不超过 10,000
进阶：如果输入的数字是作为 无限流 逐个输入如何处理？换句话说，内存不能存储下所有从流中输入的数字。您可以有效地解决吗？

法1 动态规划

思路
本题目属于基本类型1：时间序列型。所以按照套路，定义状态如下：
dp[i][j]: 第i天状态j:
  • j=0 到当前元素为止没有行驶翻转权力的最大连续1的长度
  • j=1到当前元素为止，行驶了翻转权力的最大连续1的长度。可能是当前轮行驶翻转，也可能是之前轮翻转。
状态转移如下：
notion imagenotion image
if nums[i] == 1:
		dp[i][0] = dp[i-1][0] + 1
		dp[i][1] = dp[i-1][1] + 1 
else:
		dp[i][0] = 0  # 没有行驶翻转权力 直接变为0
		dp[i][1] = dp[i-1][0] # 本轮行驶了翻转权力，可以在上一轮未行驶翻转权的基础上续一秒
题解
class Solution:
    def findMaxConsecutiveOnes(self, nums: List[int]) -> int:
        dp = [[0] * 2 for _ in nums]
        # dp[i][1] 以nums[i]结尾的 不翻转的 最长 1 
        # dp[i][0] 以nums[i]结尾的 翻转的 最长 1 
        if nums[0] == 1:
            dp[0] = [1, 1]
        else:
            dp[0] = [1, 0]

        res = 1
        for i in range(1, len(nums)):
            if nums[i] == 0:
                dp[i][1] = 0
                dp[i][0] = dp[i-1][1] + 1
            else:
                dp[i][1] = dp[i-1][1] + 1
                dp[i][0] = dp[i-1][0] + 1

            res = max(res, *dp[i])
        # print(dp)
        return res
优化：只用到了上一时刻的状态，因此可以写作如下：
class Solution:
    def findMaxConsecutiveOnes(self, nums: List[int]) -> int:
        if nums[0] == 1:
            dp_0, dp_1 = [1, 1]
        else:
            dp_0, dp_1 = [1, 0]

        res = 1
        for i in range(1, len(nums)):
            _dp_0, _dp_1 = 0, 0
            if nums[i] == 0:
                _dp_1 = 0
                _dp_0 = dp_1 + 1
            else:
                _dp_1 = dp_1 + 1
                _dp_0 = dp_0 + 1

            dp_0, dp_1 = _dp_0, _dp_1
            res = max(res, dp_0, dp_1)
        return res

法2 滑动窗口

思路
窗口内为该窗口内1的个数，当该窗口内的0的个数大于1了，就收缩窗口
题解
class Solution:
    def findMaxConsecutiveOnes(self, nums: List[int]) -> int:
        l, r = 0, 0
        wds = 0
        res = 0
        while r < len(nums):
            wds += nums[r]
            r += 1
            # 只能删除一次， 需要删除的次数 大于1了，就收缩窗口
            while wds < r - l - 1:
                wds -= nums[l]
                l += 1

            res = max(res, r-l)

        return res