Skip to content

Latest commit

 

History

History
144 lines (113 loc) · 6.91 KB

1004.md

File metadata and controls

144 lines (113 loc) · 6.91 KB
title description keywords
1004. 最大连续1的个数 III
LeetCode 1004. 最大连续1的个数 III题解，Max Consecutive Ones III，包含解题思路、复杂度分析以及完整的 JavaScript 代码实现。
LeetCode
1004. 最大连续1的个数 III
最大连续1的个数 III
Max Consecutive Ones III
解题思路
数组
二分查找
前缀和
滑动窗口

1004. 最大连续1的个数 III

🟠 Medium  🔖  数组 二分查找 前缀和 滑动窗口  🔗 力扣 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 最多可以摧毁的敌人城堡数目 数组 双指针 🟢 🀄️ 🔗