最大连续1的个数 II
难度:
标签:
题目描述
代码结果
运行时间: 51 ms, 内存: 16.4 MB
/*
题目:最大连续1的个数 II
题目思路:
使用Java Stream和辅助数组来解决这个问题。
首先计算出每个0的位置,然后计算每对相邻0之间的1的数量。
用一个数组记录每个0位置的1的数量,然后找到包含1个0的最长子数组。
*/
import java.util.Arrays;
import java.util.List;
import java.util.stream.Collectors;
public class Solution {
public int findMaxConsecutiveOnes(int[] nums) {
List<Integer> zeroIndices = Arrays.stream(nums)
.boxed()
.collect(Collectors.toList())
.stream()
.filter(num -> num == 0)
.collect(Collectors.toList());
if (zeroIndices.isEmpty()) {
return nums.length;
}
int[] zeroCounts = new int[zeroIndices.size() + 1];
for (int i = 0; i < zeroIndices.size(); i++) {
int start = i == 0 ? 0 : zeroIndices.get(i - 1) + 1;
int end = zeroIndices.get(i);
zeroCounts[i] = end - start;
}
zeroCounts[zeroCounts.length - 1] = nums.length - zeroIndices.get(zeroIndices.size() - 1) - 1;
int maxCount = 0;
for (int i = 0; i < zeroCounts.length - 1; i++) {
maxCount = Math.max(maxCount, zeroCounts[i] + zeroCounts[i + 1] + 1);
}
return maxCount;
}
}
解释
方法:
该题解使用滑动窗口的思路来解决问题。使用两个指针 left 和 right,left 指向当前连续 1 的起始位置,right 向右扩展窗口。当遇到 0 时,计算当前窗口的长度,更新结果 res,然后将 left 移动到 right 的位置,继续向右扩展窗口。最后返回 res 和 left 中的最大值,即为最长连续 1 的长度。
时间复杂度:
O(n)
空间复杂度:
O(1)
代码细节讲解
🦆
题解中提到的逻辑`遇到0,扩展右边界`是否意味着算法只在遇到0的情况下更新结果?如果数组中没有0会怎么样?
▷🦆
在算法中,当 right 指针扩展完成后,left 指针是如何更新的?请解释`left = right - i - 1`这一步骤的逻辑和意图。
▷🦆
算法最后返回`max(res, left)`的原因是什么?是否有可能在循环结束时 left 指针对应的连续1的数量大于之前记录的 res?
▷🦆
在题解中,为何将 left 初始化为0,而不是1,尤其是考虑到数组开头可能就是1的情况?
▷相关问题
最大连续 1 的个数
给定一个二进制数组 nums
, 计算其中最大连续 1
的个数。
示例 1:
输入:nums = [1,1,0,1,1,1] 输出:3 解释:开头的两位和最后的三位都是连续 1 ,所以最大连续 1 的个数是 3.
示例 2:
输入:nums = [1,0,1,1,0,1] 输出:2
提示:
1 <= nums.length <= 105
nums[i]
不是0
就是1
.
最大连续1的个数 III
给定一个二进制数组 nums
和一个整数 k
,如果可以翻转最多 k
个 0
,则返回 数组中连续 1
的最大个数 。
示例 1:
输入:nums = [1,1,1,0,0,0,1,1,1,1,0], K = 2 输出:6 解释:[1,1,1,0,0,1,1,1,1,1,1] 粗体数字从 0 翻转到 1,最长的子数组长度为 6。
示例 2:
输入:nums = [0,0,1,1,0,0,1,1,1,0,1,1,0,0,0,1,1,1,1], K = 3 输出:10 解释:[0,0,1,1,1,1,1,1,1,1,1,1,0,0,0,1,1,1,1] 粗体数字从 0 翻转到 1,最长的子数组长度为 10。
提示:
1 <= nums.length <= 105
nums[i]
不是0
就是1
0 <= k <= nums.length