0487. 最大连续1的个数 II #

标签：数组、动态规划、滑动窗口
难度：中等

题目大意 #

给定一个二进制数组，可以最多将 1 个 0 翻转为 1。

要求：找出其中最大连续 1 的个数。

解题思路 #

暴力做法是尝试将每个位置的 0 分别变为 1，然后统计最大连续 1 的个数。但这样复杂度就太高了。

我们可以使用滑动窗口来解决问题。保证滑动窗口内最多有 1 个 0。具体做法如下：

设定两个指针：left、right，分别指向滑动窗口的左右边界，保证滑动窗口内最多有 1 个 0。使用 zero_count 统计窗口内 1 的个数。使用 ans 记录答案。

一开始，left、right 都指向 0。
如果 nums[right] == 0，则窗口内 1 的个数 + 1。
如果该窗口中 1 的个数多于 1 个，即 zero_count > 1，则不断右移 left，缩小滑动窗口长度，并更新窗口中 1 的个数，直到 zero_count <= 1。
维护更新最大连续 1 的个数。然后右移 right，直到 right >= len(nums) 结束。
输出最大连续 1 的个数。

代码 #

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


class Solution:
    def findMaxConsecutiveOnes(self, nums: List[int]) -> int:
        left, right = 0, 0
        ans = 0
        zero_count = 0

        while right < len(nums):
            if nums[right] == 0:
                zero_count += 1
            while zero_count > 1:
                if nums[left] == 0:
                    zero_count -= 1
                left += 1
            ans = max(ans, right - left + 1)
            right += 1

        return ans