485. 最大连续 1 的个数

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

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

输入：nums = [1,0,1,1,0,1]
输出：2

暴力循环

代码

//
// Created by mxz on 2022/12/4.
//
#include 
#include using namespace std;class Solution {
public:int findMaxConsecutiveOnes(vector &nums) {int s = nums.size();int c = 0;int r = 0;for (int i = 0; i < s; ++i) {if (nums[i] == 1) {c++;}if (nums[i] == 0 || i == s - 1) {r = max(c, r);c = 0;}}return r;}
};int main() {Solution solution;/// vector 向量（Vector）是一个封装了动态大小数组的顺序容器（Sequence Container），顺序序列，动态数组，能够感知内存分配器的（Allocator-aware）/// vector list;  vector list1 = list2, vector list2(list); vector list = {1, 2, 3};/// vector list2(list.begin()+2,list.end()-1); vector list(7); vector list5(7, 3);vector vecTemp = {1, 1, 0, 1, 1, 1};vector list2(vecTemp.begin() + 2, vecTemp.end() - 1);vector::iterator it;for (it = list2.begin(); it != list2.end(); it++) {cout << *it << endl;}for (int i = 0; i < list2.size(); ++i) {}cout << solution.findMaxConsecutiveOnes(list2) << endl;return 0;
}

0
1
1
2

时间复杂度 O(n) n 为数组长度, 空间复杂度为 O(1)。

滑动窗口

1. 设定连个指针first和second.为了确定什么时候开始计数，需要定义一个标志位flag;
2. 先保持first不变，移动second,当遇到第一个1的时候，将second的下标赋值给first,并将标志位设置为1,即fisrt=second,flag= 1;
3. 当Second遇到0并且flag = 1 的时候，flag=1是为了保证是在元素为1的滑动窗口中。此时，计算窗口中元素1的个数，然后将flag = 0;
4. 当遍历完元素的时候，为了避免最后一个元素没有被处理，因此在循环结束是需要在计算下元素的个数。

代码

	int findMaxConsecutiveOnes(vector &nums) {int first = 0, second = 0, ans = 0, flag = 0;/// 0, 1, 1, 0while (second < nums.size()) {if (nums[second] == 1 && flag == 0) {first = second;flag = 1;} else if (nums[second] == 0 && flag) {ans = max(ans, second - first);flag = 0;}second++;}if (nums[first] == 1 && flag) {ans = max(ans, second - first);}return ans;}

时间复杂度 O(n) n 为数组长度, 空间复杂度为 O(1)。