485.最大连续1的个数(双指针,滑动窗口)
程序员文章站
2022-04-16 15:59:46
题目链接分析方法一:一次遍历(双指针)题目的约束让这个问题变得简单,使得我们可以在一次遍历解决它。算法:用一个计数器 count 记录 1 的数量,另一个计数器 maxCount记录当前最大的 1 的数量。当我们遇到 1 时,count 加一。当我们遇到0时:将 count 与 maxCount 比较,maxCoiunt 记录较大值。将 count 设为 0。返回 maxCount。class Solution { public int findMaxConsecut...
题目
分析
方法一:一次遍历(双指针)
题目的约束让这个问题变得简单,使得我们可以在一次遍历解决它。
算法:
- 用一个计数器
count
记录1
的数量,另一个计数器maxCount
记录当前最大的1
的数量。 - 当我们遇到
1
时,count
加一。 - 当我们遇到
0
时:- 将
count
与maxCount
比较,maxCoiunt
记录较大值。 - 将
count
设为0
。
- 将
- 返回
maxCount
。
class Solution {
public int findMaxConsecutiveOnes(int[] nums) {
int count = 0;
int maxCount = 0;
for(int i = 0; i < nums.length; i++) {
if(nums[i] == 1) {
// Increment the count of 1's by one.
count += 1;
} else {
// Find the maximum till now.
maxCount = Math.max(maxCount, count);
// Reset count of 1.
count = 0;
}
}
return Math.max(maxCount, count);
}
}
复杂度分析
- 时间复杂度:O(N)。N值得是数组的长度。
- 空间复杂度:O(1),仅仅使用了
count
和maxCount
。
方法二:
-
在 Python 中可以使用
map
和join
来解决此问题。 -
使用
splits
函数在0
处分割将数组转换成字符串。 -
在获取子串的最大长度就是最大连续
1
的长度。 -
Python
def findMaxConsecutiveOnes(self, nums):
return max(map(len, ''.join(map(str, nums)).split('0')))
方法三:滑动窗口
滑动窗口思路:
当输出或比较的结果在原数据结构中是连续排列的时候,可以使用滑动窗口算法求解。
将两个指针比作一个窗口,通过移动指针的位置改变窗口的大小,观察窗口中的元素是否符合题意。
- 初始窗口中只有数组开头一个元素。
- 当窗口中所有元素为 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);
}
}
执行用时:执行用时 : 1 ms, 在所有 Java 提交中击败了 100.00% 的用户
本文地址:https://blog.csdn.net/weixin_43314519/article/details/107451372
上一篇: Thread:线程顺序执行的四种方式
下一篇: C++实验三——类和对象