LeetCode第1004题 Max Consecutive Ones III说实话我一开始刷到它的时候并没有太当回事以为又是一道“找最长连续1”的送分题。结果在C语言里按自己第一版朴素写法交上去直接被一个超长用例打回原形这才意识到这道题真正的考点根本不在“连续1”而在“如何把翻转k个0这个限制优雅地融进滑动窗口的维护逻辑里”。这篇文章我想完整复盘一下这道题从暴力思路到双指针解法的推导过程包括我在C语言实现里踩过的几个实打实的坑。不管你是正在刷LeetCode热题100的求职者还是单纯想巩固滑动窗口模型的老手这篇内容都会围绕一个问题展开给定一个只含0和1的数组 nums最多允许把 k 个 0 翻转成1怎么找出最长的连续1子数组长度。文章会先从暴力枚举讲起再一步步推导出最优解法最后附上完整的C语言实现和几道同源变种题帮你把这一整类题目一次性吃透。1. 题面里的三个隐藏信息为什么这道题被归类为中等很多人在读题的时候只记住了“翻转k个0”和“最长连续1”这两个关键词却忽略了题目里的几个细节而这些细节恰恰决定了整个解法的走向。先说第一个数组只包含0和1。看上去像废话但它意味着我们在统计窗口状态时只需要关心一个数字——窗口里0的个数不需要维护任何更复杂的数据结构。第二个细节是 k 的取值范围题目并没有保证 k 一定小于数组中0的总数这就会出现一种极端情况k足够大以至于整个数组都可以被视为全1此时答案就是数组长度本身。第三个隐藏信息才是最重要的题目要求的输出是一个长度值不是某个具体的子数组起始位置或下标。这意味着我们不需要真的去“翻转”任何0只需要判断某个窗口是否满足“最多k个0”的条件。这种只求最优值、不求具体方案的题目天然就是滑动窗口或者二分的舒适区。我也见过很多人一上来就纠结一个问题到底翻哪些0这个思路很容易把人带进沟里。因为翻转方案本身是动态的一个0可能在这个窗口里需要翻换一个窗口就不用翻如果我们按照“选定一个翻转集合”去贪心复杂度会非常难看。正确的心智模型应该是把所有翻转看成延迟决策先假设窗口合法当窗口里0的数量超过k再去移动左边界“撤销”某些翻转。这道题被定为中等不是因为实现代码复杂而是因为它需要一次思维上的转换把“翻转k个0”转化为“窗口内0的数量不超过k”。这个转换一旦完成代码量其实很小但如果思维转换不过来很容易写出回溯枚举翻转组合的灾难性代码。后面我会详细展开暴力解法为什么不可行以及滑动窗口的单调性究竟从哪来。1.1 从样例出发建立直观感觉LeetCode官方给的示例是nums [1,1,1,0,0,0,1,1,1,1,0], k 2期望输出是6。我建议你手动画一下这个数组不要急着看答案。用双指针的思路走一遍右指针从头往尾扫当窗口内的0达到3个时左指针被迫右移把最早的那个0吐出去然后窗口重新回到合法状态。这个“进一个出两个”的过程本质上就是在维护一个尽可能宽的合法窗口。我当时手动模拟完这个例子之后最大的感触是窗口的滑动不是“我觉得该滑了”才滑而是“窗口内0的数量超过k”这个硬条件带来的必然结果。右指针每走一步窗口条件就发生一次变化左指针只会在条件被打破的时候被动调整。这个被动调整的过程就是双指针算法里常说的“贪心收缩”。2. 暴力枚举的两条死路为什么面试官听到这种方案会皱眉先聊聊最容易想到的方案也不怕丢人我自己第一次思考这道题的时候满脑子都是“枚举翻转方案”。既然最多翻转k个0那就从所有0的位置里选出不超过k个组合把对应的0改成1然后扫描数组找最长连续段。听起来很直接但组合数是C(m, 1) C(m, 2) ... C(m, k)m是数组中0的总数。在极端情况下m接近10^5、k接近m/2这个组合数直接天文数字连跑完第一层循环都不太现实。2.1 方案一组合枚举翻转位置假设数组长度为n把所有0的下标收集到数组pos里再对这些下标做DFS或者位掩码枚举选出不超过k个位置进行翻转。每选出一组就重新扫描一遍数组统计最大连续1长度。这个方案的复杂度至少是O(C(m, k) * n)当n100000、m50000、k25000时任何机器都会直接崩溃。LeetCode虽然没有明说数据范围的上限但10^5级别的输入就是希望你把复杂度压到O(n log n)以内C(m, k)这种指数增长的方案从一开始就不该被认真考虑。2.2 方案二枚举左端点向右扩展第二个暴力方案就“温和”多了固定窗口的左端点left从left开始向右扫描用一个变量记录窗口里已经遇到的0的数量一旦超过k就停止记录当前长度。然后left右移一位重复这个流程。这个方案严格来说是O(n²)的因为在最坏情况下比如全数组都是0每个左端点都要向右扫到数组尽头。我拿n100000的全0数组试过这个方案在本机跑了大概3秒多提交到LeetCode直接超时。O(n²)为什么在这个题目里不可接受因为当窗口合法时我们其实反复扫描了同一段区间。left0时扫过1到nleft1时又扫过2到n中间大量重叠计算。滑动窗口之所以能从O(n²)降到O(n)核心就是复用——右边界的扩展不回头左边界的收缩只减不增每个元素最多被访问两次。这个“每个元素最多访问两次”的说法是我判断一个方案是不是真·滑动窗口的直觉标准。2.3 为什么必须换脑筋暴力方案的问题不在于“算得慢”而在于它们把这道题当成了一个组合优化问题。但仔细观察题目就会发现我们并不关心翻转的是哪几个0只关心最后窗口能拉多长。既然不关心具体翻转集合就没必要为翻转集合建立状态空间。所有需要维护的信息只有窗口内0的个数。这种“不关心内部方案只关心某类计数是否越界”的题目几乎都是滑动窗口的信号。另外我还想多说一句在真实面试里如果你先说暴力思路再主动优化到滑动窗口面试官会认为你有清晰的复杂度意识但如果直接甩一个O(n²)就结束大概率会被追问“能不能更快”。所以暴力方案可以作为热身但一定要在纸面上把复杂度算给面试官看然后顺势引出滑窗。3. 滑动窗口推导从“翻转k个0”到“窗口内最多k个0”的关键一步开始写代码之前先把思维模型彻底理清。假设当前我们盯住一个子数组区间 [left, right]如果这个区间里0的个数小于等于k那么这些0全都可以被翻转成1整个区间就变成了一段连续的1。换句话说任何满足“0的个数 k”的窗口都能在翻转后形成一段连续1。题目的答案就是所有这些合法窗口的最大长度。这里有一个容易被忽略的细节我们不需要真正把窗口里的0改成1。因为翻转操作不会改变窗口的物理长度只会改变窗口在“逻辑上”看上去是否全1。我们统计的是窗口长度这个长度与“翻转动作”无关只与窗口边界有关。所以算法的任务就变成了找到一对 left、right满足窗口内0的个数不超过k并且让 right - left 1 尽量大。3.1 单调性是双指针能工作的基石有了合法窗口的定义滑动窗口的正确性依赖一个关键性质固定右端点时左端点越往左窗口越长但窗口内0的个数也越多左端点越往右窗口越短0的个数越少。所以当某一个 [left, right] 窗口内0的数量超过了k我们唯一需要做的事情就是增大left直到窗口内0的数量回到k以内。这个“只增不减”的移动方向保证了left和right都只需要单向移动整体复杂度O(n)。为什么不能先把右指针往前“试探”一下因为当前窗口已经不合法了右指针再前进只会让0的数量继续增加不可能让窗口重新合法。只有收缩左边界才有可能把超出的0剔除出去。这就是滑动窗口不像暴力回溯的根本原因它不需要回退只需要在条件被破坏时执行一次“冷静的收缩”。3.2 两种窗口更新的写法辨析滑动窗口的实现细节里有一个常见的分叉点当窗口内0的数量超过k时left应该收缩到什么位置。有两种写法写法A标准双指针使用 while (zeros k)在循环里逐步left每移动一位都同步更新zeros直到zeros回到k。写法B优化后的“一次到位”因为left一次最多只能“吐掉”一个元素而这个元素不一定是0所以没法一步到位把zeros减到k。除非你记录窗口内每个0的位置直接跳到第zeros-k个0的下一个位置。后者需要额外空间没必要。我在C语言实现里选的是写法A。while循环定的收缩条件不是“立即恢复合法”而是“直到恢复合法为止”这保证了无论遇到连续多少个0窗口收缩都能正确完成。更重要的是这样的写法天然符合“左边界只向右移动”的原则不需要依赖任何前缀数组内存占用O(1)。3.3 顺带一提二分答案也是可行解很多人不知道这道题还能用二分答案做。思路是二分窗口长度len然后判断是否存在一个长度为len的窗口其内部0的数量不超过k。为了快速判断任意区间的0的数量可以预先计算前缀和数组。单次判断O(n)二分O(log n)整体O(n log n)。这个复杂度同样能通过LeetCode而且思路很稳。那我为什么不推荐二分作为首选因为双指针解法在编码量和常数上都有优势而且滑动窗口是更多同类型题目的通用解法。但二分答案的思想值得掌握因为后续有一类问法“想达到长度L最少需要翻转几次”会用到它那道题的“反方向”就适合二分。刷题不能只背一种解法能在一个题上同时看到滑窗和二分对面试帮助很大。4. C语言实现核心代码与三个让人抓狂的细节终于到代码环节。C语言实现这道题最大的好处是没有容器类的心理负担直接用数组和两个int指针就能完成。下面是我最终提交通过的版本先贴整体代码再逐段解释。int longestOnes(int* nums, int numsSize, int k) { int left 0; int zeros 0; int ans 0; for (int right 0; right numsSize; right) { if (nums[right] 0) { zeros; } while (zeros k) { if (nums[left] 0) { zeros--; } left; } int len right - left 1; if (len ans) { ans len; } } return ans; }整个函数的逻辑只有十几行但每一个点都有讲究。left指向当前窗口的左边界初始为0zeros用来记录窗口内0的总数ans保存截至目前找到的最大合法窗口长度。外层for循环用right遍历数组每次把nums[right]纳入窗口如果是0就增加zeros。4.1 收缩逻辑为什么必须放在更新答案之前窗口收缩的判断时机是把nums[right]纳入后如果zeros k说明当前窗口已经超过翻转能力上限必须先收缩左边界。收缩过程中如果nums[left]是0那么离开窗口的0会让zeros减1然后left无条件右移一位。注意这里left的移动是无条件的——不管移出去的是0还是1窗口都必须继续收缩直到满足zeros k。这个顺序不能反。如果先更新答案再做while收缩那么任何一次非法窗口的长度都会被记录下来导致答案偏大。我在第一次提交时就犯了这个错误把len的更新写在了while (zeros k)之前结果在k2的用例上输出了比正确答案大1的数值。原因很简单那个时刻的窗口里其实有3个0根本不可能通过翻转全部变成连续1。4.2 三个让C语言初学者破防的细节第一个细节是while和if的选择。收缩左边界时必须用while而不是if。假设窗口里连续出现多个0比如[0, 0, 1]且k0右指针扫到第三个元素时zeros2一个if (zeros k)只移一次左指针zeros不会归零窗口依然非法。用while才能保证收缩彻底。这个错误在把代码从伪代码翻译成C语言时特别容易犯因为伪代码里往往写的是“移动left直到条件满足”。第二个细节是zeros的维护必须与nums[left]的实际值同步。有些人在收缩时直接zeros--因为觉得窗口变小了0就一定减少这在大脑里模拟简单用例时好像成立但一旦left移出的是1zeros根本不该变。正确逻辑必须写成条件判断if (nums[left] 0) zeros--;。我见过有人为了省这个判断把收缩条件改成while (nums[left] 0 zeros k)那样更错因为当左边界是1时窗口永远不会收缩。第三个细节是ans的更新位置。我习惯放在while收缩完成之后因为此刻的窗口是合法窗口right - left 1才是有资格参与比较的候选长度。也有人会在for循环开头先用“当前最长 max(当前最长, right - left)”来更新但那种写法要求你非常清楚每个阶段的状态语义不然很容易引入“窗口内多了一个尚未处理的非法0”之类的偏差。最稳的做法就是先纳入新元素再修正窗口最后计算长度。4.3 用两个特殊样例验证边界条件写完代码别急着提交先自己跑两个边界样例。第一个nums [0,0,0,0], k 0。此时所有元素都是0窗口内zeros一直大于kleft会被推到right1的位置right - left 1恒为0最终ans0正确。第二个nums [0,0,0,0], k 100。此时zeros永远不会超过k整个数组都是一个合法窗口最终ans4正确。这两个样例分别覆盖了“完全无法翻转”和“翻转额度完全冗余”两个极端跑通它们基本能验证主循环的稳定性。5. 隐藏的考点与同源变种一道题如何带出一类题刷题最忌讳的就是单纯背答案。1004这道题真正的价值在于它和一系列LeetCode题目共享同一个底层模板维护一个窗口窗口内某类元素的计数不超过给定上限求最大窗口长度。如果你能从这个抽象层理解它那么遇到下面几道题都会变得非常顺手。5.1 同源题目对照表我自己在刷题过程中整理了一张对照表建议你也建立自己的版本题目核心变化窗口限制条件解法要点1004 最大连续1的个数 III最多翻转k个0窗口内0的数量 k双指针滑动窗口487 最大连续1的个数 II最多翻转1个0窗口内0的数量 1就是k1的10042024 考试的最大困扰度最多改k个字符窗口内F或T的数量 k两个窗口分别跑424 替换后的最长重复字符最多改k个字符窗口内非多数元素数量 k维护窗口字符频次3 无重复字符的最长子串窗口内字符不重复窗口内所有字符频次 1哈希表或数组频次这张表的共同点在于代码框架几乎一致外层循环都是for right中间都是根据条件更新状态遇到违规就收缩left最后计算长度。区别只在于“用什么变量记录窗口状态”。1004用zeros计数424用字符频次的最大值3用每个字符的出现次数。建立起这个“变体意识”后每道题的思考时间会大幅缩短。5.2 如果把问题反过来问二分答案的用武之地面试官大概率会在你给出滑动窗口解法后追加一个问题如果我不问“最多翻k次能有多长”而是问“想要得到长度为L的连续1最少需要翻转几次”你该怎么办这个问题的暴力做法是对每个长度为L的窗口统计0的数量取最小值复杂度O(n)。但更优雅的做法是二分L然后用一个“窗口内0的数量是否小于等于k”的判定函数去验证。这和1004的滑动窗口共享同一个窗口状态定义只是外层从“枚举右端点找最长”变成了“二分长度做校验”。我在实际刷题过程中很喜欢这种“正反互推”的练习方式。同一个窗口定义正向做滑窗得到最长长度反向做二分得到临界长度两种方法叠加在一起能帮你把这个模型理解得更扎实。特别是面对面试手写代码时多掌握一种思路就是多一分底气。5.3 这道题在真实工程中的影子有些人可能会问LeetCode这种题除了面试到底有什么用我个人的观点是Max Consecutive Ones III这种“允许一定容错的最长连续段检测”模式在数据处理场景中确实有对应物。比如在日志分析中你需要找出一段最长的时间区间其中异常片段的数量不超过某个阈值或者在信号质量评估中允许一定比例的干扰点后找出最长的连续稳定信号段。这些场景的共同特征是你关心的不是单点质量而是整体区间在容错条件下的最大跨度。当然工程实现时往往还会叠加时间窗口、数据流在线处理等额外要求但核心的“双指针维护计数”思想是共通的。这也是我觉得滑动窗口值得反复刷的原因它不仅仅是一个面试考点更是一种处理连续区间问题的基本素养。5.4 我的最终建议动手重写比多看十篇题解有用回到1004这道题本身我觉得最重要的建议就是看完这篇文章后不要直接抄代码先合上页面自己写一遍。写的时候重点关注三个点zeros的增减时机、while收缩的完整度、ans更新是否在收缩之后。如果你能在不参考源码的情况下列出这三个点的正确顺序那这道题才算是真正掌握了。之后再去刷487、2024、424这三道姊妹题用同一套代码框架去套遇到差异点再停下来想想为什么。我在最开始刷这道题时曾经因为while (zeros k)错写成if (zeros k)连续提交了两次都是Wrong Answer。第三次我老老实实打开调试器盯着left、right、zeros三个变量的变化过程才真正看懂了“一次非法窗口的收缩可能要挪动多个左边界位置”这件事。从那以后我再也没有在这类题上犯过同样的错。也希望你能在一次次的调试里把这些细节变成本能反应而不是靠背题过关。