跳至主要內容

0487. 最大连续1的个数 II

ITCharge大约 1 分钟

0487. 最大连续1的个数 IIopen in new window

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

题目大意

给定一个二进制数组,可以最多将 10 翻转为 1

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

解题思路

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

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

设定两个指针:leftright,分别指向滑动窗口的左右边界,保证滑动窗口内最多有 10。使用 zero_count 统计窗口内 1 的个数。使用 ans 记录答案。

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

代码

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