LeetCode 1493. 删掉一个元素以后全为 1 的最长子数组
题目描述
题意分析
输入只包含 0 和 1，必须删除恰好一个元素，使删除后某段连续的 1 尽可能长。删除一个 0 能把它两侧的 1 接起来；即使整个数组都是 1，也必须删掉其中一个，不能直接返回原长度。
解法：最多一个 0 的滑动窗口
核心思路
[!blue]
一次删除最多消除一个 0，所以能被一次删除变成全 1 的原数组区间，最多只能含一个 0。若区间有一个 0，就删除它；若没有 0，就删除其中一个 1。两种情况得到的长度都是区间长度减一，因此目标可以转成寻找“最多含一个 0”的最长窗口。
统一减一也不会漏掉“在全 1 区间外删除”的答案：只要这段 1 没有占满整个原数组，就可以把窗口向相邻位置扩展一个元素，再删除这个元素，保留原来的全部 1。扩展后的窗口仍最多含一个 0，同样会被扫描覆盖；如果已经占满整个数组，必须删除一个 1。
维护窗口
[left, right]和其中的zeroCount。加入右端后，如果零的数量超过一个，就不断移出左端元素，直到只剩至多一个零。缩到这里立即停止，保留的是以当前right结尾的最长合法窗口：更早的左端还会包含两个零，不可能成为答案。加入新元素不会让被排除的更早左端重新合法，所以
left只需向右移动。每个右端点都取到自己的最长合法窗口，再用right-left更新答案；它正好等于窗口长度right-left+1减去必删的一项。
解题步骤
- 初始化
left = 0、zeroCount = 0、ans = 0，让right从左到右扫描。- 若新加入的元素是 0，先增加
zeroCount。- 当
zeroCount > 1时，若移出的nums[left]是 0 就减少计数，然后执行left++，直到窗口合法。- 用
right-left更新ans，遍历结束后返回答案。全为 1 时窗口会扩展到整个数组，得到
n-1；全为 0 时合法窗口最多长 1，得到 0；单个元素无论是 0 还是 1，删除后也得到 0，不需要额外分支。
代码实现
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个位置。- 空间复杂度：$O(1)$，边界与零计数。
关键点总结
[!green]
- 窗口只表示删除前的候选区间，不需要实际删除或修改数组。
- 删除与翻转不同：被删除的位置不再占长度，所以答案必须减一。
- 每次收缩都恰好排除无法靠一次删除消除全部零的左端点，不会跳过更优解。
易错点总结
[!yellow]
- 按窗口原长返回，会把全一输入多算一。
- 不允许窗口含零，无法合并零两侧的一。
- 先移动左端再统计移出值，会错读新的边界项。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 487. 最大连续1的个数 II | 中等 | 原题最多翻一个0，本题必须删一个位置，因此全1数组也要让长度减1。 |
| 1004. 最大连续1的个数 III | 中等 | 可以借用至多一个0的窗口，但答案还需扣除被删的那个位置。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！