485. Max Consecutive Ones

 

Given a binary array, find the maximum number of consecutive 1s in this array.

Example 1:

**Input:** [1,1,0,1,1,1]
**Output:** 3
**Explanation:** The first two digits or the last three digits are consecutive 1s.
    The maximum number of consecutive 1s is 3.

Note:

  • The input array will only contain 0 and 1.
  • The length of input array is a positive integer and will not exceed 10,000

 

这道题让求最大连续1的个数,不是一道难题。可以遍历一遍数组,用一个计数器 cnt 来统计1的个数,方法是如果当前数字为0,那么 cnt 重置为0,如果不是0,cnt 自增1,然后每次更新结果 res 即可,参见代码如下:

 

解法一:

class Solution {
public:
    int findMaxConsecutiveOnes(vector<int>& nums) {
        int res = 0, cnt = 0;
        for (int num : nums) {
            cnt = (num == 0) ? 0 : cnt + 1;
            res = max(res, cnt);
        }
        return res;
    }
};

 

由于是个二进制数组,所以数组中的数字只能是0或1,那么连续1的和跟个数相等,所以可以计算和,通过加上 num,再乘以 num 来计算,如果当前数字是0,那么 sum 就被重置为0,还是要更新结果 res,参见代码如下:

 

解法二:

class Solution {
public:
    int findMaxConsecutiveOnes(vector<int>& nums) {
        int res = 0, sum = 0;
        for (int num : nums) {
            sum = (sum + num) * num;
            res = max(res, sum);
        }
        return res;
    }
};

 

Github 同步地址:

https://github.com/grandyang/leetcode/issues/485

 

类似题目:

Max Consecutive Ones II

Max Consecutive Ones III

 

参考资料:

https://leetcode.com/problems/max-consecutive-ones/

https://leetcode.com/problems/max-consecutive-ones/discuss/96693/Java-4-lines-concise-solution-with-explanation

 

LeetCode All in One 题目讲解汇总(持续更新中…)


转载请注明来源于 Grandyang 的博客 (grandyang.com),欢迎对文章中的引用来源进行考证,欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论,也可以邮件至 grandyang@qq.com

💰


微信打赏


Venmo 打赏

×

Help us with donation