LeetCode 1493. 删掉一个元素以后全为 1 的最长子数组
目录
题目描述
题意分析
给一个只含 0 和 1 的数组，必须从中删掉恰好一个元素，然后求剩下的数组里全为 1 的最长连续子数组长度。
「必须删除一个」是这题最容易读漏的地方。哪怕数组本来就全是 1，也不能不删——所以答案会比数组长度少 1。反过来，删掉的那个元素可以是 1 也可以是 0，只是删 0 显然更划算。
换个角度看：删掉一个元素后剩下的全 1 段，在原数组里对应的是一段「最多含一个 0，且那个 0 就是被删掉的元素」的连续区间。所以目标可以重述为：找一段最多含一个 0 的连续区间，答案是它的长度减 1。
约束信号：数组长度上限 $10^5$，元素只有 0 和 1。规模要求线性或接近线性；「连续区间 + 计数上限」的组合是滑动窗口的典型形态。
边界情况：数组全为 0 时，任何区间删掉一个 0 后剩下的还是 0，答案为 0；数组全为 1 且长度为 $n$ 时，答案是 $n - 1$；长度为 1 时答案必为 0。
解法：最多一个 0 的滑动窗口
核心思路
问题关键：题目要求「恰好删除一个元素」。若原数组的一个连续窗口最多含一个 0，删掉这个 0；若窗口里没有 0，就删掉一个 1。两种情况得到的全 1 长度都等于「窗口长度减一」。因此问题等价于：寻找最多含一个 0 的最长窗口。
选法依据：右端点右移时，窗口内 0 的数量只会增加；一旦超过 1，右移左端点就能恢复合法，且左端点无需回退。这种单调的区间约束正适合滑动窗口，两个指针各扫描一次。
窗口不变量：处理完每个
right后，[left, right]内至多有一个 0，zeroCount与窗口内 0 的数量一致，并且left是保持窗口合法的最小左端点。因此，当前窗口是以right结尾的最长合法窗口。正确性：每个合法窗口都能通过一次删除得到「窗口长度减一」个连续 1；反过来，任意可行答案在原数组中都来自一个至多含一个 0 的窗口。算法考察了每个右端点对应的最长合法窗口，所以不会漏掉最优解。代码用
right - left更新答案，恰好已经扣除了必须删除的一个元素。边界：全 1 数组长度为 $n$ 时返回 $n-1$；全 0 数组和长度为 1 的数组返回 0。这些情况都由同一套窗口逻辑自然覆盖。
解题步骤
- 初始化左边界
left = 0、零计数zeroCount = 0、答案ans = 0。答案初值取 0，正好覆盖「全 0 数组」和「长度为 1」这两种应返回 0 的情形。- 右边界
right从 0 扫到末尾。每次先把nums[right]纳入窗口：若它是 0 就让zeroCount加一。先扩右再收左，是滑动窗口的标准节奏。- 当
zeroCount > 1时持续收缩左边界：先根据nums[left]更新零计数，再右移left。本实现用while保证更新答案前窗口已经合法，因为移动一次未必越过前一个 0。- 收缩完成后用
right - left更新答案。这里减 1 已经隐含在式子里，不要写成right - left + 1。- 遍历结束返回
ans。整个过程中left只增不减，所以两个指针各走一遍数组。例子：
nums = [0,1,1,1,0,1,1]。右端点走到第二个 0 时，窗口含两个 0，左端点越过第一个 0 后恢复合法；最终窗口[1, 6]的长度为 6，删掉其中的 0 后得到 5 个连续 1。若输入是[1,1,1]，窗口虽没有 0，仍必须删掉一个 1，所以答案是 2。
代码实现
class Solution {
public int longestSubarray(int[] nums) {
int left = 0;
int zeroCount = 0;
int ans = 0;
for (int right = 0; right < nums.length; right++) {
if (nums[right] == 0) {
zeroCount++;
}
while (zeroCount > 1) {
if (nums[left] == 0) {
zeroCount--;
}
left++;
}
// 必须删除一个元素，所以合法窗口贡献长度为窗口长度减一。
ans = Math.max(ans, right - left);
}
return ans;
}
}
func longestSubarray(nums []int) int {
left := 0
zeroCount := 0
ans := 0
for right, num := range nums {
if num == 0 {
zeroCount++
}
for zeroCount > 1 {
if nums[left] == 0 {
zeroCount--
}
left++
}
// 必须删除一个元素，所以合法窗口贡献长度为窗口长度减一。
if right-left > ans {
ans = right - left
}
}
return ans
}
复杂度分析
- 时间复杂度：$O(n)$。右指针从头走到尾共 $n$ 步，左指针同样只增不减、总移动量不超过 $n$ 步，每步做常数次判断，所以是线性的而不是二重循环的 $O(n^2)$。
- 空间复杂度：$O(1)$。只维护了左边界、零计数和答案三个整型变量，没有前缀和数组也没有额外容器。
关键点总结
- 先把「删除一个元素」改写成「窗口内最多允许一个 0」，再套滑动窗口；这是从操作问题转成区间约束的关键。
- 窗口能成立，是因为右移左端点只会让 0 的数量减少，约束具有单调性。
zeroCount必须始终与当前窗口同步：移出左端元素后再移动指针。- 面试时要主动解释
right - left：合法窗口长度是right - left + 1，题目又强制删除一个元素，因此结果统一少 1，不必区分窗口里有没有 0。- 与「最多翻转一个 0」不同，本题发生的是删除，删除后数组拼接，所以答案要比对应窗口长度少 1。
易错点总结
- 忘记强制删除：用
right - left + 1更新答案。[1,1,1]会错误返回 3，正确答案是 2。- 窗口不允许 0：一出现 0 就收缩。
[1,1,0,1,1]会被拆成两段，无法得到删除中间 0 后的答案 4。- 先更新答案再收缩：
[1,0,0,1]在右端点到达第二个 0 时，非法窗口会先贡献长度 2；正确答案只有 1。必须先恢复窗口不变量，再计算答案。- 计数与指针错位：先执行
left++再检查移出的元素，会检查到新左端点，导致zeroCount失真。- 混淆删除与翻转：
[1,1,0,1,1]若翻转 0 可得长度 5，删除 0 只能得长度 4。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 485. 最大连续 1 的个数 | 简单 | 不允许任何修改，单变量计数即可 |
| 面试题 05.03. 翻转数位 | 简单 | 输入是整数的二进制位，需先按位取出再滑窗 |
| 487. 最大连续1的个数 II | 中等 | 允许翻转一个 0，长度不减 1 |
| 1004. 最大连续1的个数 III | 中等 | 翻转上限推广到 $k$ 个，窗口约束参数化 |
| 424. 替换后的最长重复字符 | 中等 | 字符集扩大到 26，需维护窗口内出现次数最大值 |