每日一练：LeeCode-485. 最大连续 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 <= 10^5
• nums[i] 不是 0 就是 1.

思路

双指针

• 首先初始化最长连续1的个数 res 为0。
• 然后通过一个 for 循环遍历数组中的每一个元素，以每一个元素作为起始点进行检查。
• 在循环中，首先将右指针 right 初始化为左指针 left 的位置。
• 然后进入一个内部的 while 循环，该循环用于将右指针 right 向右移动，直到遇到0或到达数组末尾为止。
• 在 while 循环中，检查右指针所指向的元素是否为1，如果是1，则右指针向右移动，直到遇到0或到达数组末尾。
• 当遇到0或到达数组末尾时，计算当前连续1的个数，并更新最长连续1的个数 res。
• 最后将左指针 left 更新为右指针 right 的位置，即下一个连续1的起始位置。
• 循环继续，直到遍历完整个数组。
• 最后返回最长连续1的个数 res。

class Solution {
    public int findMaxConsecutiveOnes(int[] nums) {
        int res = 0; // 初始化最长连续1的个数为0
        for (int left = 0; left < nums.length; left++) { // 遍历数组中的每一个元素
            int right = left; // 将右指针初始化为左指针的位置
            while (right < nums.length && nums[right] == 1) right++; // 右指针向右移动直到遇到0或到达数组末尾
            res = Math.max(res, right - left); // 更新最长连续1的个数
            left = right; // 将左指针更新为右指针的位置，即下一个连续1的起始位置
        }
        return res; // 返回最长连续1的个数
    }
}

贪心算法

• 首先初始化最长连续1的个数 max 和临时计数器 temp 都为0。
• 通过一个 for 循环遍历数组中的每一个元素。
• 在循环中，首先检查当前元素是否为1，如果是1，则临时计数器 temp 加1，表示遇到了连续的1。
• 如果当前元素为0，则表示连续的1被断开，将临时计数器 temp 重置为0，重新开始计数连续的1。
• 每次更新临时计数器 temp 的值后，使用 Math.max() 方法将 max 更新为当前最大值，即连续1的最大长度。
• 循环结束后，返回最长连续1的个数 max。

class Solution {
    public int findMaxConsecutiveOnes(int[] nums) {
        int max = 0; // 初始化最长连续1的个数为0
        int temp = 0; // 初始化临时计数器为0
        for (int i = 0; i < nums.length; i++) { // 遍历数组中的每一个元素
            if (nums[i] == 1) { // 如果当前元素为1
                temp++; // 临时计数器加1
            } else { // 如果当前元素为0
                temp = 0; // 重置临时计数器为0，表示当前断开了连续的1
            }
            max = Math.max(max, temp); // 更新最长连续1的个数
        }
        return max; // 返回最长连续1的个数
    }
}