leetcode
leetcode 451 ~ 500
最大连续1的个数 II

最大连续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会怎么样?
题解中的逻辑`遇到0,扩展右边界`确实主要描述了在遇到0时如何处理和更新结果,这是因为0的出现可能中断连续的1序列。如果数组中没有0,该算法的循环会依然遍历整个数组,但因为没有0,i指针会连续前进,left会一直增加直到数组末尾。此时,left将记录整个数组的长度(如果全为1的话),这也会在最后通过`max(res, left)`得到正确的最大连续1的个数,即整个数组的长度。
🦆
在算法中,当 right 指针扩展完成后,left 指针是如何更新的?请解释`left = right - i - 1`这一步骤的逻辑和意图。
在题解中,`left = right - i - 1`这一步骤发生在找到一个0后,right指针尝试跳过这个0并继续向前找连续的1。这一步骤的目的是为了更新left计数器,以反映在当前0之后的新一段连续1的长度。`right - i - 1`是因为right现在指向的是新段连续1的结束位置的下一个位置,减去i(当前0的位置)再减去1得到的是从i+1位置开始到right位置之前的1的数量,即新一段连续1的长度。
🦆
算法最后返回`max(res, left)`的原因是什么?是否有可能在循环结束时 left 指针对应的连续1的数量大于之前记录的 res?
算法最后返回`max(res, left)`的原因在于考虑到数组末尾可能存在一段连续的1,这段连续1直到数组结束都没有被更长的序列打断。在这种情况下,left将会持续增加直到数组末尾,而如果在遍历过程中没有更新更大的res值,left可能会是最大的连续1的数量。因此,使用`max(res, left)`确保无论数组是否以1结束,都能返回正确的最大值。
🦆
在题解中,为何将 left 初始化为0,而不是1,尤其是考虑到数组开头可能就是1的情况?
在题解中,left初始化为0是因为在算法开始时,还没有遇到任何1,因此连续1的计数应从0开始。当遇到第一个1时,left会增加1,正确记录连续1的数量。如果left初始化为1,那么即使数组开头不是1,left的计数也会错误地高估。因此,初始化为0是为了精确地根据实际遇到的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,如果可以翻转最多 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