1004. 最大连续1的个数 III

1004. 最大连续1的个数 III #

  • 标签:双指针、滑动窗口
  • 难度:中等

题目大意 #

给定一个由 0、1 组成的数组 nums,再给定一个整数 k。最多可以将 k 个值从 0 变到 1。返回仅包含 1 的最长连续子数组的长度。

解题思路 #

使用滑动窗口的方法来做。使用两个指针 left、right 指向数组开始位置。使用 max_count 来维护仅包含 1 的最长连续子数组的长度。

不断右移 right 指针,扩大滑动窗口范围,并统计窗口内 0 元素的个数,直到 0 元素的个数超过 k 时将 left 右移,缩小滑动窗口范围,并减小 0 元素的个数。并维护 max_count。

代码 #

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
class Solution:
    def longestOnes(self, nums: List[int], k: int) -> int:
        max_count = 0
        zero_count = 0
        left, right = 0, 0
        while right < len(nums):
            if nums[right] == 0:
                zero_count += 1
            right += 1
            if zero_count > k:
                if nums[left] == 0:
                    zero_count -= 1
                left += 1
            max_count = max(max_count, right - left)
        return max_count
本站总访问量  次  |  您是本站第  位访问者