最大连续1的个数III

🎯 问题描述（来源于LeetCode）

描述：
给定一个二进制数组 nums 和一个整数 k，假设最多可以翻转 k 个 0 ，则返回执行操作后 数组中连续 1 的最大个数 。
说明：

  • 1 <= nums.length <= 105

  • nums[i] 不是 0 就是 1

  • 0 <= k <= nums.length
    示例：

  • 示例 1：

1
2
3
4
输入：nums = [1,1,1,0,0,0,1,1,1,1,0], K = 2
输出：6
解释：[1,1,1,0,0,1,1,1,1,1,1]
粗体数字从 0 翻转到 1，最长的子数组长度为 6。
  • 示例 2：
1
2
3
4
输入：nums = [0,0,1,1,0,0,1,1,1,0,1,1,0,0,0,1,1,1,1], K = 3
输出：10
解释：[0,0,1,1,1,1,1,1,1,1,1,1,0,0,0,1,1,1,1]
粗体数字从 0 翻转到 1，最长的子数组长度为 10。

💻 解题思路

思路1：可变长度滑动窗口

思路1：代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
    def longestOnes(self, nums: List[int], k: int) -> int:
        left,right=0,0
        n={0:0,1:0}
        l =0
        while right<len(nums):
            n[nums[right]]+=1
            while n[0]>k:
                n[nums[left]]-=1
                left+=1
            l=max(l,n[1]+n[0])
            right+=1
        return l

思路1：📊 性能分析

提交结果
  • 运行时间：159ms击败5.81%
  • 内存消耗：21.87MB击败33.56%
复杂度验证
  • 时间复杂度：O(N)O(N)
  • 空间复杂度：O(1)O(1)

思考