当前位置： 移动技术网 > IT编程>脚本编程>Python > 【LeetCode】485.最大连续1的个数（双指针，滑动窗口）

【LeetCode】485.最大连续1的个数（双指针，滑动窗口）

2020年07月20日  | 移动技术网IT编程  | 我要评论

题目

链接

image-20200719200434631

分析

方法一：一次遍历（双指针）

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

算法：

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

您可能感兴趣的文章:

如对本文有疑问， 点击进行留言回复！！

相关文章:

验证码：
最近更新的文章
大家感兴趣的文章
移动技术网