LeetCode 1004：最大连续1的个数 III（滑动窗口） —— 题解

欢迎阅读一.题目1004. 最大连续1的个数 III - 力扣LeetCode​ 欢迎来到「最大连续1的个数 III」题解之旅本文将带你从“翻转最多 k 个 0 来获得最长连续 1”这一实际场景出发深入理解滑动窗口双指针的灵活运用并掌握如何通过维护窗口内 0 的个数不超过 k来高效求解最大窗口长度。在开始之前建议你先了解题目背景这是 LeetCode 1004 题给定一个二进制数组nums和一个整数k允许将最多 k 个 0 翻转成 1求翻转后数组中连续 1 的最大个数。本质上我们要找到一个最长的连续子数组使得其中 0 的个数不超过 k因为我们可以把这些 0 全部翻转为 1从而得到一段全 1 的连续区间。明确学习目标掌握滑动窗口核心流程——右指针right不断向右扩展每遇到一个 0 就增加窗口内 0 的计数如果计数超过k则移动左指针left缩小窗口直到窗口内 0 的个数 ≤ k在此过程中不断更新窗口长度的最大值。理解为什么这种“右扩左缩”的策略能遍历所有可能的窗口并保证找到最优解同时熟练处理边界情况如k0或全为 1。准备好环境建议在本地 IDE 或 LeetCode 在线编辑器中打开代码边看边运行亲手验证示例如nums [1,1,1,0,0,0,1,1,1,0], k 2输出6。本文将从问题转化、滑动窗口策略设计0 计数约束、窗口收缩条件到代码实现层层递进。即使你对滑动窗口还不熟悉我们也会从“维护一个最多包含 k 个 0 的窗口并尝试拉长它”这一直觉出发让你轻松抓住核心思想——窗口内 0 的数量是唯一限制条件用双指针动态调整窗口使窗口在满足条件时尽可能长。现在让我们一起在二进制数组中滑动窗口找出翻转后最长的连续 1 吧 二.做题思路一、问题分析前置分析给定一个二进制数组nums和一个整数k最多可以将k个 0 翻转为 1求翻转后最长的连续 1 的子数组长度。核心观察等价于寻找一个最长的子数组使得其中 0 的个数不超过k。这符合滑动窗口的特性因为窗口内 0 的个数随右指针扩展而增加随左指针收缩而减少。二、算法策略滑动窗口使用左右指针left和right维护窗口变量zero记录窗口内 0 的个数。右指针right从 0 到 n-1 依次遍历将nums[right]加入窗口若为 0 则zero。若zero k则收缩左指针left同时若移出的是 0 则zero--直到zero k。每次调整后更新最长窗口长度len max(len, right - left 1)。示例执行过程nums [1, 1, 0, 0, 1, 1, 1, 0, 1, 1],k 2步骤rightnums[right]入窗后zerozero k?操作收缩当前窗口[left, right]窗口长度len更新初始--0----01010否-[0,0]112110否-[0,1]223201否-[0,2]334302否-[0,3]445412否-[0,4]556512否-[0,5]667612否-[0,6]778703是左移移除nums[0]1zero仍为3继续移除nums[1]1仍为3移除nums[2]0zero--变为2left3[3,7]57保持9812否-[3,8]67保持10912否-[3,9]77保持最终len 7对应子数组[1, 1, 1, 0, 1, 1, 1]通过翻转两个 0 为 1实际上原窗口[3,9]包含两个 0翻转后全为1长度为7。三、正确性说明简单版本滑动窗口始终维护包含最多k个 0 的连续子数组。当窗口内 0 的个数超过k时必须移动左指针直到满足条件因为继续扩展右指针不会减少 0 的个数。这种“不满足就收缩”的策略保证了在右指针固定的情况下当前窗口是以该右端点为结尾的最长有效子数组。遍历所有右端点记录最大值即可得到全局最优解。由于每个元素最多入窗出窗一次算法正确且高效。四、实现细节边界防护初始化left 0right 0zero 0len 0。for (int right 0; right n; right)遍历若nums[right] 0zerowhile (zero k)循环若nums[left] 0zero--left更新len max(len, right - left 1)。若n 0直接返回 0但题目保证 n ≥ 1。时间复杂度 O(n)空间复杂度 O(1)。五、返回值目标映射返回len即翻转后最长连续 1 的个数。三.代码#include iostream #include vector #include algorithm using namespace std; class Solution { public: int longestOnes(vectorint nums, int k) { // 算法思路滑动窗口双指针 // 维护一个窗口 [left, right]使得窗口内 0 的个数不超过 k。 // 右指针不断向右扩展每遇到一个 0 就增加 zero 计数 // 如果 zero 超过 k则左指针右移同时如果左指针移出的是 0则 zero 减 1。 // 在每次调整后更新窗口长度right - left 1记录最大值。 int n nums.size(); int zero 0; // 当前窗口内 0 的个数 int len 0; // 记录满足条件的最长窗口长度 // 双指针 left 和 right 定义窗口 [left, right] for (int left 0, right 0; right n; right) { // 入窗口将 nums[right] 加入窗口 if (nums[right] 0) { zero; // 如果是 0增加窗口内 0 的计数 } // 判断条件如果窗口内 0 的个数超过 k则需要收缩左边界 while (zero k) { // 出窗口将 nums[left] 移出窗口 if (nums[left] 0) { zero--; // 如果移出的是 0减少计数 } left; // 左指针右移缩小窗口 } // 更新结果当前窗口满足条件0 的个数 k计算窗口长度 len max(len, right - left 1); } // 返回最长连续 1 的个数即满足条件的最大窗口长度 return len; } }; int main() { // 测试用例示例 1期望输出 6 vectorint nums {1, 1, 1, 0, 0, 0, 1, 1, 1, 0}; int k 2; Solution sol; int result sol.longestOnes(nums, k); cout result endl; // 输出 6 return 0; }四、易错点分析难点一for循环中right自增与窗口收缩的先后顺序for (int left 0, right 0; right n; right) { if (nums[right] 0) { zero; } while (zero k) { /* 收缩左边界 */ } len max(len, right - left 1); }为什么容易困惑常规滑动窗口有时会在收缩后才更新len但这里每次right扩展后立即入窗口然后收缩最后才更新长度。难点在于len的更新是在while收缩之后这意味着当前窗口始终是“合法”的0 的个数 ≤ k因此可以直接用right - left 1。初学者可能误以为应该在入窗口前或收缩前更新长度而本代码利用“先入后缩”的顺序保证了更新时窗口已合法这是理解上的关键转折点。难点二zero计数与left移出元素的关联while (zero k) { if (nums[left] 0) { zero--; } left; }核心难点zero只记录当前窗口内 0 的个数但当left右移时需要判断移出的元素是否为 0。这里容易混淆的是left移动后zero的减少仅发生在移出元素是 0 的情况下如果移出的是 1zero不变。这个逻辑虽简单但在调试时容易因为遗漏if判断而误以为left每动一次zero都要减 1导致计数错误。理解“只减移出的 0”是掌握本算法的前提。难点三窗口长度的更新位置与最大值的维护len max(len, right - left 1);难点在于为什么放在这里因为经过while收缩后窗口[left, right]一定满足zero ≤ k此时窗口内所有 0 都可以通过翻转变成 1所以当前窗口长度就是一个可行解。初学者可能认为只需在right扩展时更新一次但若left发生了移动窗口长度会变化必须每次收缩后重新计算才能保证不遗漏更优解。这个位置强调了“每次调整后都取最大”的思想。五、流程图 闭幕 恭喜你完成了「最大连续1的个数 III」问题的学习为了巩固知识并进一步拓展建议你动手实践在 LeetCode 上提交代码尝试不同的测试用例。深入思考本题使用滑动窗口维护一个0 的个数不超过 k的区间右指针不断扩展当窗口内 0 的个数超过 k 时移动左指针。请问为什么当 zero k 时只需要移动一次左指针就可以继续能否一次性跳到更远的位置代码中当nums[right] 0时zero当nums[left] 0时zero--。为什么只统计 0 的数量而不需要统计 1 的数量如果k 0问题退化为求最长连续 1 子数组当前算法是否仍然正确请验证。滑动窗口的时间复杂度为O(n)因为每个元素最多被左右指针各访问一次。如果数组长度n 10^5这个算法是否高效本题要求最多翻转 k 个 0相当于将窗口内的 0 视为“可以容忍的”。如果要求最多可以删除 k 个元素不限定 0 或 1使剩余部分中连续 1 最长算法应如何调整延伸挑战如果问题改为最多翻转 k 个 1使连续 0 最长代码只需改动哪一处即可如果数组中的数字不只是 0 和 1而是包含多种取值例如颜色分类中的 0,1,2要求通过最多 k 次修改使得某种指定值连续最长你会如何设计通用的滑动窗口框架如果你觉得本文对你有所帮助欢迎点赞 / 收藏关注作者获取更多题解留言交流你的疑问或优化思路深入思考答案只移动一次左指针即可因为滑动窗口的特性是每次右指针移动一步左指针也至多移动一步保证窗口始终合法且每个位置作为窗口起点最多被考虑一次这是 O(n) 的基础。一次性跳到更远位置虽可行但会增加代码复杂度且不利于维护窗口连续性。只需统计 0 的数量因为窗口内 1 的数量 窗口长度 - 0 的数量而翻转 0 后都变成 1连续 1 的长度就是窗口长度所以只要 0 的个数 ≤ k窗口长度就是答案无需额外统计 1。k0时zero 0 立即收缩左指针窗口内始终保持 0 的个数为 0即窗口内全为 1算法退化为求最长连续 1 子数组逻辑正确。O(n) 对n10^5非常高效完全可接受。若允许删除任意 k 个元素问题变为求删除 k 个元素后最长连续 1 子数组本质上仍然是容忍 k 个非 1 元素只需将判断条件改为统计窗口内非 1 的个数即可逻辑相同。延伸挑战答案挑战1只需将判断条件从nums[right] 0改为nums[right] 1zero改为统计 1 的个数即可其余逻辑不变即可求最长连续 0 子数组。挑战2将统计条件改为目标值以外的元素计数即bad当nums[right] ! target收缩时判断bad k即可实现通用滑动窗口适用于任意离散取值的数组。祝你在算法之路上越走越稳早日攻克每一道难题下次见 ✨