- 标签:数组、动态规划、滑动窗口
- 难度:中等
描述:给定一个二进制数组
要求:如果最多可以翻转一个
说明:
- 1 <= nums.length <= 105 nums[i] 不是 0 就是 1.
示例:
- 示例 1:
输入:nums = [1,0,1,1,0]
输出:4
解释:翻转第一个 0 可以得到最长的连续 1。当翻转以后,最大连续 1 的个数为 4。
- 示例 2:
输入:nums = [1,0,1,1,0,1]
输出:4
暴力做法是尝试将每个位置的
我们可以使用滑动窗口来解决问题。保证滑动窗口内最多有
设定两个指针:$left$、$right$,分别指向滑动窗口的左右边界,保证滑动窗口内最多有
- 一开始,$left$、$right$ 都指向
$0$ 。 - 如果
$nums[right] == 0$ ,则窗口内$1$ 的个数加$1$ 。 - 如果该窗口中
$1$ 的个数多于$1$ 个,即$zero\underline{}count > 1$ ,则不断右移$left$ ,缩小滑动窗口长度,并更新窗口中$1$ 的个数,直到$zero\underline{}count \le 1$ 。 - 维护更新最大连续
$1$ 的个数。然后右移$right$ ,直到$right \ge 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
-
时间复杂度:$O(n)$,其中
$n$ 为数组$nums$ 的长度。 - 空间复杂度:$O(1)$。