欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

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...

题目

链接

485.最大连续1的个数(双指针,滑动窗口)

分析

方法一:一次遍历(双指针)

题目的约束让这个问题变得简单,使得我们可以在一次遍历解决它。

算法:

  • 用一个计数器 count 记录 1 的数量,另一个计数器 maxCount记录当前最大的 1 的数量。
  • 当我们遇到 1 时,count 加一。
  • 当我们遇到0时:
    • countmaxCount 比较,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),仅仅使用了 countmaxCount

方法二:

  • 在 Python 中可以使用 mapjoin 来解决此问题。

  • 使用 splits 函数在 0 处分割将数组转换成字符串。

  • 在获取子串的最大长度就是最大连续 1 的长度。

  • Python

def findMaxConsecutiveOnes(self, nums):
  return max(map(len, ''.join(map(str, nums)).split('0')))

方法三:滑动窗口

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

  1. 初始窗口中只有数组开头一个元素。
  2. 当窗口中所有元素为 1 时,右指针向右移,扩大窗口。
  3. 当窗口中存在 0 时,计算连续序列长度,左指针指向右指针。
    485.最大连续1的个数(双指针,滑动窗口)
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

相关标签: LeetCode