【每日一题】LeetCode #485 最大连续 1 的个数

晓

发布于 2020-04-05

在计算机领域，算法是一个永恒的主题。任何计算机使用者都希望计算机能运行得更快一些或是能解决更大规模的问题。从现在开始，跟随我每天刷一道算法题吧！

在此之前，我们刷的几乎都是有关数组操作的算法题。在接下来的几天里，我们将学习 “双指针技巧”，它可以帮助我们解决许多与数组相关的问题。

双指针专题第五天。

LeetCode #485 最大连续 1 的个数

题目

给定一个二进制数组，计算其中最大连续1的个数。

示例1：

输入: [1,1,0,1,1,1]
输出: 3
解释: 开头的两位和最后的三位都是连续1，所以最大连续1的个数是 3.

注意：

输入的数组只包含 0 和1。
输入数组的长度是正整数，且不超过 10,000。

解题思路

常规思路：

首先来说一说非双指针解法，这道题的一种常规做法就是遍历数组，记录连续1的个数，比较是否是当前最大个数。

常规遍历代码：

class Solution {
    public int findMaxConsecutiveOnes(int[] nums) {
        int length = nums.length;
        int max  = 0;
        int count = 0;
        
        // 遍历数组
        for (int i = 0; i < length; i++){
            if (nums[i] == 1){
                // 记录连续1的个数
                count++;
            }else {
                // 比较是否是当前最大个数
                if (count > max)
                    max = count;
                // 归零，寻找下一个连续序列
                count = 0;
            }
        }
        // 因为最后一次连续序列在循环中无法比较，所以在循环外进行比较
        return max > count?max:count;
    }
}

滑动窗口思路：

继续昨天的双指针应用——滑动窗口算法，这道题依然可以使用滑动窗口算法。

当输出或比较的结果在原数据结构中是连续排列的时候，可以使用滑动窗口算法求解。
将两个指针比作一个窗口，通过移动指针的位置改变窗口的大小，观察窗口中的元素是否符合题意。

初始窗口中只有数组开头一个元素。
当窗口中所有元素为 1 时，右指针向右移，扩大窗口。
当窗口中存在 0 时，计算连续序列长度，左指针指向右指针。

滑动窗口代码：

class Solution {
    public int findMaxConsecutiveOnes(int[] nums) {
        int length = nums.length;
        int left = 0;
        int right = 0;
        int maxSize = 0;
        
        while(right < length){
            //当窗口中所有元素为 1 时，右指针向右移，扩大窗口。
            if (nums[right++] == 0){
                //当窗口中存在 0 时，计算连续序列长度，左指针指向右指针。
                maxSize = Math.max(maxSize, right - left - 1);
                left = right;
            }
        }
        // 因为最后一次连续序列在循环中无法比较，所以在循环外进行比较
        return Math.max(maxSize, right - left);
    }
}

【每日一题】LeetCode #3 无重复字符的最长字串

在计算机领域，算法是一个永恒的主题。任何计算机使用者都希望计算机能运行得更快一些或是能解决更大规模的问题。从现在开始，跟随我每天刷一道算法题吧！在此之前，我们刷的几乎都是有关数组操作的...

【每日一题】LeetCode #209 长度最小的子数组