给定一个二进制数组,你可以最多将 1 个 0 翻转为 1,找出其中最大连续 1 的个数。
示例 1:
输入:[1,0,1,1,0] 输出:4 解释:翻转第一个 0 可以得到最长的连续 1。 当翻转以后,最大连续 1 的个数为 4。
注:
- 输入数组只包含
0
和1
. - 输入数组的长度为正整数,且不超过 10,000
进阶:
如果输入的数字是作为 无限流 逐个输入如何处理?换句话说,内存不能存储下所有从流中输入的数字。您可以有效地解决吗?
用 prefix[i]
数组表示以 i 结尾往前累计的最大连续 1 的个数,suffix[i]
数组表示以 i 开头往后累计的最大连续 1 的个数。
遍历 nums
数组每个为 0 的位置,则位置 i 的最大连续 1 的个数为 1 + prefix[i-1] + suffix[i+1]
。
当然,如果 nums
数组没有 0,即所有元素都是 1,那么结果即为 nums
数组的长度。
class Solution:
def findMaxConsecutiveOnes(self, nums: List[int]) -> int:
n = len(nums)
prefix = [0] * n
suffix = [0] * n
res = 0
for i in range(n):
if i == 0:
prefix[i] = nums[i]
else:
prefix[i] = 0 if nums[i] == 0 else prefix[i - 1] + 1
res = max(res, prefix[i])
for i in range(n - 1, -1, -1):
if i == n - 1:
suffix[i] = nums[i]
else:
suffix[i] = 0 if nums[i] == 0 else suffix[i + 1] + 1
for i in range(n):
if nums[i] == 0:
t = 1
if i > 0:
t += prefix[i - 1]
if i < n - 1:
t += suffix[i + 1]
res = max(res, t)
return res
- 双指针,时间复杂度 O(n²),空间复杂度 O(1)
class Solution {
public int findMaxConsecutiveOnes(int[] nums) {
int n = nums.length;
int res = 0;
for (int i = 0; i < n; ++i) {
int cnt = 1;
int j = i;
while (j < n && (cnt > 0 || nums[j] == 1)) {
if (nums[j] == 0) --cnt;
++j;
}
res = Math.max(res, j - i);
}
return res;
}
}
- 辅助数组,时间复杂度 O(n),空间复杂度 O(n)
class Solution {
public int findMaxConsecutiveOnes(int[] nums) {
int n = nums.length;
int[] prefix = new int[n];
int[] suffix = new int[n];
int res = 0;
for (int i = 0; i < n; ++i) {
if (i == 0) prefix[0] = nums[0];
else prefix[i] = nums[i] == 0 ? 0 : prefix[i - 1] + 1;
res = Math.max(res, prefix[i]);
}
for (int i = n - 1; i >= 0; --i) {
if (i == n - 1) suffix[n - 1] = nums[n - 1];
else suffix[i] = nums[i] == 0 ? 0 : suffix[i + 1] + 1;
}
for (int i = 0; i < n; ++i) {
if (nums[i] == 0) {
int t = 1;
if (i > 0) t += prefix[i - 1];
if (i < n - 1) t += suffix[i + 1];
res = Math.max(res, t);
}
}
return res;
}
}