leetcode
leetcode 401 ~ 450
最大连续 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.

代码结果

运行时间: 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?
在遇到0时确实会进行一次比较并可能更新max_n,这样可以记录下到目前为止找到的最大连续1的个数。然而,如果数组的最后一个元素是1或整个数组都是1,那么遍历结束时,n中存储的连续1的个数将不会在遇到0时被比较更新到max_n中。因此,遍历结束后需要再比较一次n和max_n,以确保这种情况下,连续1的最大数量被正确记录。
🦆
在代码中,你是如何确保即使数组全部由1组成时,也能正确返回最大连续1的个数的?
代码中通过初始化n为0并在每次遇到数字1时增加n的值,持续统计连续1的个数。重要的是,由于最后一次循环结束后可能不会遇到0来触发max_n的更新(尤其是当数组全部由1组成时),因此在循环结束后再次比较n和max_n的值,确保即使数组全部由1组成也能通过n>max_n的比较,将最终的连续1的个数正确更新到max_n中,然后返回max_n。
🦆
如果输入数组是空数组,这段代码是否能够正确处理?如果不能,应如何修改代码以处理这种边界情况?
如果输入的数组是空数组,当前的代码实现可以正确处理。由于数组中没有元素,循环不会执行,n和max_n都将保持初始值0。因此,函数将返回0,这是正确的结果,因为空数组中没有1,连续1的最大个数自然是0。
🦆
这种一次遍历的方法是否适用于所有类似求最大连续子序列的问题,或者它有什么潜在的局限性?
这种一次遍历的方法非常适合于求解最大连续1的个数这类问题,因为它简单且直接。然而,对于更复杂的最大连续子序列问题,如需要处理不仅包括1和0,还包括其他数字,或者需要求最大连续子序列的和等,这种方法可能需要调整或完全改变。例如,求最大子数组和通常使用Kadane算法,该算法虽然也是一次遍历,但处理逻辑更复杂,涉及到当前子数组和的重置和最大值的更新。因此,这种方法的适用性取决于问题的具体要求和复杂性。

相关问题

最大连续1的个数 II

最大连续1的个数 II

最大连续1的个数 III

给定一个二进制数组 nums 和一个整数 k,如果可以翻转最多 k0 ,则返回 数组中连续 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