最大连续 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
.
代码结果
运行时间: 31 ms, 内存: 16.3 MB
/*
* 思路:
* 使用Java Stream对数组进行处理。首先将数组转换为流,
* 然后通过StringBuilder将所有元素连接成一个字符串,再以"0"为分隔符分割。
* 统计每个分割后的字符串的长度,找到其中的最大值。
*/
import java.util.Arrays;
public class Solution {
public int findMaxConsecutiveOnes(int[] nums) {
return Arrays.stream(String.join("", Arrays.stream(nums)
.mapToObj(String::valueOf)
.toArray(String[]::new))
.split("0"))
.mapToInt(String::length)
.max()
.orElse(0);
}
}
解释
方法:
这个题解使用了一次遍历的方法。通过一个变量n来记录当前连续1的个数,另一个变量max_n来记录遍历过程中出现过的最大连续1的个数。遍历数组,如果当前元素为1,则n加1;如果当前元素为0,则比较n和max_n的大小,取较大值更新max_n,并将n重置为0。遍历结束后,再比较一次n和max_n的大小,取较大值作为最终结果返回。
时间复杂度:
O(n)
空间复杂度:
O(1)
代码细节讲解
🦆
题解中在遇到0时会比较并可能更新max_n,为何遍历结束后还需要再比较一次n和max_n?
▷🦆
在代码中,你是如何确保即使数组全部由1组成时,也能正确返回最大连续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