题目描述
思路解析动画文字版
记住「窗口最多留一个 0、答案取 right − left(长度减一,因为必须删一个)」,下面每一格都在套它。
这一行是 0/1 数组。窗口从空开始,右指针从左往右一格格扩,我们盯着窗口里有几个 0、以及答案 ans 怎么变。
右指针到第 0 位(值 0)。它是个 0,现在窗口里有 1 个 0。没超过 1 个,窗口合法。
窗口 [0, 0] 合法,长 1。必须删一个,所以这一段贡献的是 1−1 = 0。没超过已有的最长 0,保持。
右指针到第 1 位(值 1)。它是个 1,现在窗口里有 1 个 0。没超过 1 个,窗口合法。
窗口 [0, 1] 合法,长 2。必须删一个,所以这一段贡献的是 2−1 = 1。比之前长,最长刷新成 1。
右指针到第 2 位(值 1)。它是个 1,现在窗口里有 1 个 0。没超过 1 个,窗口合法。
窗口 [0, 2] 合法,长 3。必须删一个,所以这一段贡献的是 3−1 = 2。比之前长,最长刷新成 2。
右指针到第 3 位(值 1)。它是个 1,现在窗口里有 1 个 0。没超过 1 个,窗口合法。
窗口 [0, 3] 合法,长 4。必须删一个,所以这一段贡献的是 4−1 = 3。比之前长,最长刷新成 3。
右指针到第 4 位(值 0)。它是个 0,现在窗口里有 2 个 0。超过 1 个了(红),下一步要左缩,把多出来的 0 移出去。
把左指针右移 1 步、移出途中那个 0,窗口收成 [1, 4],又只剩 1 个 0。窗口长 4,删掉里面一个元素后是 3。没超过已有的最长 3,保持。
右指针到第 5 位(值 1)。它是个 1,现在窗口里有 1 个 0。没超过 1 个,窗口合法。
窗口 [1, 5] 合法,长 5。必须删一个,所以这一段贡献的是 5−1 = 4。比之前长,最长刷新成 4。
右指针到第 6 位(值 1)。它是个 1,现在窗口里有 1 个 0。没超过 1 个,窗口合法。
窗口 [1, 6] 合法,长 6。必须删一个,所以这一段贡献的是 6−1 = 5。比之前长,最长刷新成 5。
右指针到第 7 位(值 0)。它是个 0,现在窗口里有 2 个 0。超过 1 个了(红),下一步要左缩,把多出来的 0 移出去。
把左指针右移 4 步、移出途中那个 0,窗口收成 [5, 7],又只剩 1 个 0。窗口长 3,删掉里面一个元素后是 2。没超过已有的最长 5,保持。
右指针到第 8 位(值 1)。它是个 1,现在窗口里有 1 个 0。没超过 1 个,窗口合法。
窗口 [5, 8] 合法,长 4。必须删一个,所以这一段贡献的是 4−1 = 3。没超过已有的最长 5,保持。
扫完全程,最长的「最多含一个 0」窗口删掉那个元素后,得到 5 个连续的 1,就是答案。右、左指针各只走一遍,O(n)。
边界先想清:全 1 是 n−1、全 0 是 0、有 0 删 0。
面试常考:与 LC1004 的关系,以及「删除 vs 翻转」导致答案差一个。
参考代码
from typing import Listclass Solution: def longestSubarray(self, nums: List[int]) -> int: left = zeros = ans = 0 for right, x in enumerate(nums): zeros += x == 0 while zeros > 1: zeros -= nums[left] == 0 left += 1 ans = max(ans, right - left) return ans复杂度
- 时间：O(n)，左右指针各只前进一遍,每个元素进出窗口各一次
- 空间：O(1)，只用 left/zeros/ans 几个变量
易错点
面试追问把动画讲成自己的话
追问这道题和「最多翻 k 个 0 的最长连续 1(LC1004)」什么关系?
追问为什么不用真的去删某个元素再算?
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
将 x 减到 0 的最小操作数
LeetCode 1658 · 中等 · 沿着 滑动窗口套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题