1004. 最大连续1的个数 III

🟠   🔖  数组 二分查找 前缀和 滑动窗口  🔗 力扣 LeetCode

题目

Given a binary array nums and an integer k, return the maximum number of consecutive1 ' s in the array if you can flip at most k 0's.

Example 1:

Input: nums = [1,1,1,0,0,0,1,1,1,1,0], k = 2

Output: 6

Explanation: [1,1,1,0,0,1 ,1,1,1,1,1]

Bolded numbers were flipped from 0 to 1. The longest subarray is underlined.

Example 2:

Input: nums = [0,0,1,1,0,0,1,1,1,0,1,1,0,0,0,1,1,1,1], k = 3

Output: 10

Explanation: [0,0,1,1,1 ,1 ,1,1,1,1 ,1,1,0,0,0,1,1,1,1]

Bolded numbers were flipped from 0 to 1. The longest subarray is underlined.

Constraints:

• 1 <= nums.length <= 10^5
• nums[i] is either 0 or 1.
• 0 <= k <= nums.length

题目大意

给定一个二进制数组 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。

提示：

• 1 <= nums.length <= 10^5
• nums[i] 不是 0 就是 1
• 0 <= k <= nums.length

解题思路

可以使用 滑动窗口 来解答这道题：

• 使用两个指针 left 和 right 来维护一个窗口，窗口内包含最多 k 个 0。
• right 指针向右移动，扩展窗口，在每次移动 right 时，检查当前窗口内的元素。如果 nums[right] 是 0，增加当前窗口内的 0 的计数。
• 当窗口内的 0 的数量超过 k 时，移动 left 指针以缩小窗口，直到 0 的数量不再超过 k。
• 在每次迭代中计算并更新当前的最大连续 1 的长度。

复杂度分析

• 时间复杂度：O(n)，其中 n 是数组的长度，right 指针遍历数组一次，left 指针最多也会遍历一次。
• 空间复杂度：O(1)，只使用常量空间来存储指针和计数。

代码

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

	for (let right = 0; right < nums.length; right++) {
		// 当遇到 0 时，增加计数
		if (nums[right] === 0) {
			zeroCount++;
		}

		// 当窗口内的 0 的数量超过 k 时，移动 left 指针
		while (zeroCount > k) {
			if (nums[left] === 0) {
				zeroCount--;
			}
			left++;
		}

		// 更新最大长度
		maxLength = Math.max(maxLength, right - left + 1);
	}

	return maxLength; // 返回最大连续 1 的长度
};

相关题目

题号	标题	题解	标签	难度
340	至多包含 K 个不同字符的最长子串 🔒		哈希表 字符串 滑动窗口
424	替换后的最长重复字符		哈希表 字符串 滑动窗口
485	最大连续 1 的个数	[✓]	数组
487	最大连续1的个数 II 🔒		数组 动态规划 滑动窗口
1493	删掉一个元素以后全为 1 的最长子数组		数组 动态规划 滑动窗口
2024	考试的最大困扰度		字符串 二分查找 前缀和 1+
2379	得到 K 个黑块的最少涂色次数		字符串 滑动窗口
2401	最长优雅子数组		位运算 数组 滑动窗口
2461	长度为 K 子数组中的最大和		数组 哈希表 滑动窗口
2511	最多可以摧毁的敌人城堡数目		数组 双指针