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

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

示例 1：
输入：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：
输入：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。

解题思路

输入：一个二进制数组 nums 和一个整数 k，表示最多可以将 k 个 0 翻转为 1

输出：通过最多翻转 k 个 0，得到的最长连续 1 的个数

本题属于 可变长度滑动窗口类型 类型。

我们可以使用双指针维护一个滑动窗口，并用一个变量统计窗口内 0 的个数。当窗口内 0 的数量不超过 k 时，说明当前窗口是合法的，可以更新最大连续 1 的长度；当超过 k 时，就不断移动左指针缩小窗口，直到重新满足条件。

整个过程中，我们在遍历右指针的同时，动态调整窗口并记录合法窗口的最大长度，最终返回即可。

代码实现

python

class Solution:
    def longestOnes(self, nums: List[int], k: int) -> int:
        l = 0  # 左指针
        count = 0  # 当前窗口内 0 的个数
        ans = 0    # 最大长度

        for r in range(len(nums)):
            if nums[r] == 0:
                count += 1  # 碰到 0 就增加计数

            # 如果 0 的数量超过了 k，就移动左指针缩小窗口
            while count > k:
                if nums[l] == 0:
                    count -= 1
                l += 1

            # 维护最大窗口长度
            ans = max(ans, r - l + 1)

        return ans

javascript

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var longestOnes = function(nums, k) {
    let left = 0;
    let ans = 0;

    let count = 0;
    for (let right in nums) {
        if (nums[right] == 0) {
            count ++;
        }

        while (count > k) {
            if (nums[left] == 0) {
                count --;
            }
            left ++;
        }

        ans = Math.max(ans, right - left + 1);
    }

    return ans;
};

复杂度分析

时间复杂度：O(n)

空间复杂度：O(1)

链接

1004 国际版

1004 中文版