LeetCode 0485. 最大连续 1 的个数

【LetMeFly】485.最大连续 1 的个数

力扣题目链接：https://leetcode.cn/problems/max-consecutive-ones/

给定一个二进制数组 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.

方法一：统计

使用几个遍历：

• ans代表答案（也就是连续1的最大个数），初始值是0
• lastIs1代表上一个数字是否为1，初始值是false
• nowCnt代表当前“连续1”的个数，初始值是0

接下来遍历数组，如果这个元素是1，那么nowCnt就+1

如果这个元素是0并且上一个元素是1（lastIs1），那么就更新答案的最大值，并重置“nowCnt”

每次遍历完都需要更新“lastIs1”

最后，再次更新答案最大值即可（否则如果最后一个元素不是0，nowCnt就没有与ans做比较）

• 时间复杂度$O(n)$，其中$n$是数组中的元素个数
• 空间复杂度$O(1)$

AC代码

C++

class Solution {
public:
    int findMaxConsecutiveOnes(vector<int>& nums) {
        int ans = 0;
        bool lastIs1 = false;
        int nowCnt = 0;
        for(int i : nums) {
            if (i) {
                lastIs1 = true;
                nowCnt++;
            }
            else {
                if (lastIs1) {
                    lastIs1 = false;
                    ans = max(ans, nowCnt);
                    nowCnt = 0;
                }
            }
        }
        ans = max(ans, nowCnt);
        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

同步发文于CSDN，原创不易，转载请附上原文链接哦~
Tisfy：https://letmefly.blog.csdn.net/article/details/127642017