当前位置：首页 > news >正文

C++ 优选算法力扣 1004. 最大连续1的个数 II 滑动窗口（同向双指针）优化每日一题详细题解

news 2025/8/16 11:19:18

一、题目描述

题目链接：最大连续1的个数 III

题目描述：
给定一个二进制数组和一个整数，如果可以翻转最多个，则返回数组中连续的最大个数。

示例 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]，翻转中间3个0后，连续1的长度为10。

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

二、为什么这道题值得你花几分钟看懂？

最大连续1的个数 III 作为 LeetCode 第 1004 题，是 滑动窗口（双指针）算法在条件限制场景下的经典应用。它的核心价值在于：

帮你理解 “如何在滑动窗口中加入条件约束（最多翻转k个0）”，进一步深化对窗口收缩逻辑的掌握；
掌握 “动态平衡窗口内有效元素（1的数量）与约束条件（0的数量）” 的技巧，这种思路可迁移到带限制的子数组问题；
清晰区分 滑动窗口与双指针的异同，避免在解题时混淆两种方法的适用场景。

学会这道题，你能举一反三解决：

最长重复子数组（LeetCode 718）
替换后的最长重复字符（LeetCode 424）
最大连续1的个数 IV（LeetCode 1493）等问题

生活中也有类似场景，比如“视频直播中统计最多断流k次的最长连续观看时长”“工厂生产中允许最多k个残次品的最长连续合格序列”，核心都是“在约束条件下找连续区间的最大值”。

三、题目拆解：提取其中的关键点

结合问题要求和代码框架，核心要素如下：

输入是二进制数组 nums（元素非0即1）和整数 k（最多翻转的0的数量），数组长度可达 10⁵（需考虑效率）。
需找到连续子数组，其中最多包含 k 个0（翻转后可全部变为1），且长度最大。
若数组全为0且 k 大于等于数组长度，返回数组长度。

关键点提炼：

连续性：子数组元素必须连续（区别于子序列）。
约束性：窗口内0的数量不能超过 k，这是窗口收缩的核心条件。
高效性：暴力解法会超时，需优化到 O(n) 时间复杂度。
转化思维：将“最多翻转k个0”转化为“窗口内0的数量≤k”，简化问题描述。

四、明确思路：从暴力到滑动窗口

1. 暴力解法的困境

最直观的思路是枚举所有可能的连续子数组，统计其中0的数量，若≤k则记录长度，最后返回最大值。

二层循环版本：
外层循环枚举子数组起点 i（0≤i<n），内层循环枚举子数组终点 j（i≤j<n），同时统计0的数量。当0的数量>k时，跳出内层循环。时间复杂度 O(n²)，在 n=10⁵ 时会超时。
为什么不可行：
对于长度为10⁵的数组，O(n²) 意味着10¹⁰次操作，远超计算机每秒约10⁸次的处理能力，必然超时。

结论：必须找到 O(n) 级别的算法。

2. 滑动窗口的核心：用约束条件控制窗口伸缩

为什么能用滑动窗口？

数组元素非0即1，且我们关注的是连续区间内0的数量，这一数量具有可累积性：

当窗口右边界 right 右移时，若遇到0则数量+1，遇到1则不变；
当窗口左边界 left 右移时，若移除0则数量-1，移除1则不变。

这种特性让我们可以用双指针动态维护窗口，确保0的数量始终≤k，同时跟踪窗口的最大长度。

滑动窗口的思路

用 left 和 right 标记窗口的左右边界，初始都为0。
移动 right 扩大窗口，统计窗口内0的数量 mark（遇到0则+1）。
当 mark > k 时，移动 left 缩小窗口：若移除的是0则 mark-1，直到 mark ≤k。
每次调整后，计算当前窗口长度（right-left+1），更新最大长度 ret。

为什么这样正确？

当窗口 [left, right] 中0的数量≤k时：

该窗口对应的子数组可通过翻转最多k个0变为全1，是有效窗口；
扩大窗口（right 右移）可能得到更长的有效窗口，因此需要继续尝试；
当0的数量超过k时，必须收缩左边界（left 右移），直到重新满足约束。

由于 right 和 left 都只向右移动（不会回退），每个元素最多被访问2次，时间复杂度降至 O(n)。

3. 滑动窗口与双指针的异同

对比维度	滑动窗口	双指针
核心思想	维护一个满足条件的连续区间（窗口），通过伸缩边界优化效率	用两个指针分别处理不同位置，通过指针移动解决问题（可非连续）
适用场景	连续子数组/子串问题，需动态维护区间内的状态（如和、数量）	可用于连续问题（如两数之和），也可用于非连续问题（如反转字符串）
指针移动	左右指针通常同向移动（右指针扩张，左指针收缩）	指针可同向或反向移动（如二分查找中左右指针相向而行）
关联关系	滑动窗口是双指针的特殊形式，强调“连续区间”和“动态维护”	双指针是更宽泛的概念，包含滑动窗口在内的多种指针配合模式

总结：滑动窗口属于双指针的范畴，但更聚焦于“连续区间的动态维护”。当问题涉及“连续子数组/子串”且需要“根据条件调整区间范围”时，优先考虑滑动窗口；其他场景（如数组元素交换、两数匹配）可考虑普通双指针。

五、算法实现：滑动窗口（双指针）

核心逻辑：

初始化 mark=0（窗口内0的数量）、ret=0（最大长度）、left=0（左边界）、right=0（右边界）。
右指针 right 遍历数组，遇到0则 mark+1。
当 mark > k 时：
- 若左边界元素是0，则 mark-1；
- 左指针 left 右移，直到 mark ≤k。
计算当前窗口长度 right-left+1，更新 ret 为最大值。
遍历结束后，返回 ret。

六、C++代码实现：一步步拆解

完整代码（附详细注释）：

#include <vector>
#include <algorithm>  // 包含max函数
using namespace std;class Solution {
public:int longestOnes(vector<int>& nums, int k) {int mark = 0;       // 记录窗口内0的数量int left = 0;       // 窗口左边界int right = 0;      // 窗口右边界int ret = 0;        // 最大连续1的长度（翻转后）int n = nums.size();while (right < n) {// 右移右边界，遇到0则标记数+1if (nums[right] == 0) {mark++;}// 当0的数量超过k时，收缩左边界while (mark > k) {// 若左边界是0，移除后标记数-1if (nums[left] == 0) {mark--;}left++;  // 左边界右移}// 更新最大长度：当前窗口长度为right-left+1ret = max(ret, right - left + 1);right++;  // 右边界右移，继续扩大窗口}return ret;}
};

代码拆解

1. 初始化

int mark = 0;       // 统计窗口内0的数量，用于判断是否满足约束条件（≤k）
int left = 0, right = 0;  // 双指针分别标记窗口的左右边界
int ret = 0;        // 存储最大长度，初始为0
int n = nums.size();

2. 右指针遍历与窗口扩张

while (right < n) {if (nums[right] == 0) {mark++;  // 遇到0则计数+1}// ... 收缩左边界的逻辑 ...right++;  // 右指针右移，扩大窗口
}

right 从0到n-1遍历，确保每个元素都被纳入窗口考虑；
mark 实时记录窗口内0的数量，是判断窗口是否有效的核心指标。

3. 左指针收缩与约束平衡

while (mark > k) {  // 当0的数量超过允许的k个时，必须收缩窗口if (nums[left] == 0) {mark--;  // 若左边界是0，移除后计数-1}left++;  // 左指针右移，缩小窗口范围
}

循环条件：mark > k 保证窗口始终满足“最多k个0”的约束；
收缩逻辑：通过移动左指针，减少窗口内0的数量，直到重新满足约束。

4. 更新最大长度

ret = max(ret, right - left + 1);  // 每次调整后计算窗口长度，取最大值

无论窗口是否收缩，只要满足约束条件，就需计算当前长度并更新最大值；
窗口长度公式 right - left + 1 适用于闭区间 [left, right]。

示例运行过程（以示例1为例）
输入：nums = [1,1,1,0,0,0,1,1,1,1,0]，k = 2

right=0-2（元素为1）：mark=0，窗口[0,2]，长度3 → ret=3。
right=3（元素0）：mark=1 ≤2，窗口[0,3]，长度4 → ret=4。
right=4（元素0）：mark=2 ≤2，窗口[0,4]，长度5 → ret=5。
right=5（元素0）：mark=3 >2 → 进入收缩循环：
- left=0（元素1）→ left=1；
- left=1（元素1）→ left=2；
- left=2（元素1）→ left=3（元素0），mark=2 → 退出循环。
  窗口[3,5]，长度3 → ret保持5。
right=6-9（元素1）：mark=2，窗口[3,9]，长度7 → ret=7。
right=10（元素0）：mark=3 >2 → 收缩循环：
- left=3（元素0）→ mark=2，left=4 → 退出循环。
  窗口[4,10]，长度7 → ret保持7？
  （实际计算：right-left+1=10-4+1=7，与之前持平）

最终 ret=10-4+1=7？不对，重新梳理：

哦，示例1的正确输出是6，上述推演存在计算错误。正确过程中，当right=9时，窗口是[3,9]（元素[0,0,1,1,1,1]），长度7？不，原数组索引6-9是[1,1,1,1]，因此[3,9]是0,0,0,1,1,1,1（长度7），但其中0的数量是3，超过k=2，实际收缩后left会右移到4，窗口[4,9]（0,1,1,1,1）长度6，这才是正确的有效窗口。

通过动态调整，最终最大长度为6，符合示例结果。

时间复杂度

O(n)：right 和 left 都只从0移动到n-1，每个元素最多被访问2次（加入窗口和移出窗口）。

空间复杂度

O(1)：仅使用常数个额外变量（mark、left、right、ret），未使用额外空间。

七、实现过程中的坑点总结

窗口收缩的条件判断
- 错误写法：用 if 代替 while 收缩左边界（如 if (mark > k) { ... }）。
- 问题：当一次右移加入多个0时（如连续3个0，k=1），单次收缩可能无法使 mark ≤k，导致窗口无效。
- 解决：必须用 while 循环持续收缩，直到 mark ≤k。
更新最大长度的时机
- 错误写法：仅在收缩窗口后更新长度。
- 问题：未收缩的窗口（如全为1的窗口）可能是最长的，会被遗漏。
- 解决：每次右指针移动后（无论是否收缩），都需计算当前窗口长度并更新最大值。
忽略k=0的特殊情况
- 错误假设：k=0时无需处理，但实际需要统计原生连续1的最大长度。
- 验证：代码中 mark 会记录0的数量，当k=0时，mark>0 就会收缩窗口，自动适配原生1的统计，无需额外处理。
数组全为0的边界处理
- 疑问：当 nums 全为0且 k ≥n 时，是否需要特殊返回n？
- 验证：代码中窗口会扩张到整个数组，mark =n ≤k，此时长度为n，ret 会正确记录，无需额外处理。