0487. 最大连续1的个数 II
大约 1 分钟
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
的个数。
代码
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