1004. 最大连续1的个数 III

题目链接：https://leetcode.cn/problems/max-consecutive-ones-iii/

代码

/**
 * 1004. 最大连续1的个数 III
 * https://leetcode.cn/problems/max-consecutive-ones-iii/
 */

function longestOnes(nums: number[], k: number): number {
    let left = 0;
    let res = 0;
    let cnt = 0;
    for (let i = 0; i < nums.length; i++) {
        if (nums[i] === 0) {
            cnt++;
        }
        while (cnt > k) {
            if (nums[left] === 0) {
                cnt--;
            }
            left++;
        }
        res = Math.max(res, i - left + 1);
    }
    return res;
}

思路

使用滑动窗口：

• 用 cnt 记录当前窗口内 0 的个数；
• 右指针向右移动，遇到 0 时 cnt++；
• 当 cnt > k 时，移动左指针缩小窗口，直到窗口内 0 的个数不超过 k；
• 每次更新窗口长度的最大值。

时间复杂度 $O(n)$，空间复杂度 $O(1)$，其中 $n$ 为数组长度。