删掉一个元素以后全为 1 的最长子数组 图解题解
这道题到底在问什么
- 输入
- nums=[1,1,0,1]
- 输出
- 3(删中间的 0)
- 输入
- nums=[1,1,1]
- 输出
- 2(必须删一个)
最优解：一步一步想明白
- 3记住「窗口最多留一个 0、答案取 right − left(长度减一,因为必须删一个)」,下面每一格都在套它。
- 4这一行是 0/1 数组。窗口从空开始,右指针从左往右一格格扩,我们盯着窗口里有几个 0、以及答案 ans 怎么变。
- 5右指针到第 0 位(值 0)。它是个 0,现在窗口里有 1 个 0。没超过 1 个,窗口合法。
- 6窗口 [0, 0] 合法,长 1。必须删一个,所以这一段贡献的是 1−1 = 0。没超过已有的最长 0,保持。
- 7右指针到第 1 位(值 1)。它是个 1,现在窗口里有 1 个 0。没超过 1 个,窗口合法。
- 8窗口 [0, 1] 合法,长 2。必须删一个,所以这一段贡献的是 2−1 = 1。比之前长,最长刷新成 1。
- 9右指针到第 2 位(值 1)。它是个 1,现在窗口里有 1 个 0。没超过 1 个,窗口合法。
- 10窗口 [0, 2] 合法,长 3。必须删一个,所以这一段贡献的是 3−1 = 2。比之前长,最长刷新成 2。
- 11右指针到第 3 位(值 1)。它是个 1,现在窗口里有 1 个 0。没超过 1 个,窗口合法。
- 12窗口 [0, 3] 合法,长 4。必须删一个,所以这一段贡献的是 4−1 = 3。比之前长,最长刷新成 3。
- 13右指针到第 4 位(值 0)。它是个 0,现在窗口里有 2 个 0。超过 1 个了(红),下一步要左缩,把多出来的 0 移出去。
- 14把左指针右移 1 步、移出途中那个 0,窗口收成 [1, 4],又只剩 1 个 0。窗口长 4,删掉里面一个元素后是 3。没超过已有的最长 3,保持。
- 15右指针到第 5 位(值 1)。它是个 1,现在窗口里有 1 个 0。没超过 1 个,窗口合法。
- 16窗口 [1, 5] 合法,长 5。必须删一个,所以这一段贡献的是 5−1 = 4。比之前长,最长刷新成 4。
- 17右指针到第 6 位(值 1)。它是个 1,现在窗口里有 1 个 0。没超过 1 个,窗口合法。
- 18窗口 [1, 6] 合法,长 6。必须删一个,所以这一段贡献的是 6−1 = 5。比之前长,最长刷新成 5。
- 19右指针到第 7 位(值 0)。它是个 0,现在窗口里有 2 个 0。超过 1 个了(红),下一步要左缩,把多出来的 0 移出去。
- 20把左指针右移 4 步、移出途中那个 0,窗口收成 [5, 7],又只剩 1 个 0。窗口长 3,删掉里面一个元素后是 2。没超过已有的最长 5,保持。
- 21右指针到第 8 位(值 1)。它是个 1,现在窗口里有 1 个 0。没超过 1 个,窗口合法。
- 22窗口 [5, 8] 合法,长 4。必须删一个,所以这一段贡献的是 4−1 = 3。没超过已有的最长 5,保持。
- 23扫完全程,最长的「最多含一个 0」窗口删掉那个元素后,得到 5 个连续的 1,就是答案。右、左指针各只走一遍,O(n)。
⚠️ 容易写错的地方
✗ 错：答案取 right − left + 1
✓ 对：答案取 right − left
题目必须删掉一个元素,窗口长度 right−left+1 删一个就剩 right−left
✗ 错：窗口允许两个及以上 0
✓ 对：窗口最多留一个 0
删一个元素只能消掉一个 0,留两个 0 就没法全变成 1
✗ 错：全是 1 时直接返回长度
✓ 对：全是 1 也得删一个
题目要求必须删一个元素,所以全 1 时答案是 n−1
完整代码（Python / C++ / Java）
Python
from typing import List
class 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 ansC++
#include <algorithm>
#include <vector>
using namespace std;
class Solution {
public:
int longestSubarray(vector<int>& nums) {
int left = 0, zeros = 0, ans = 0;
for (int right = 0; right < (int)nums.size(); ++right) {
zeros += nums[right] == 0;
while (zeros > 1) zeros -= nums[left++] == 0;
ans = max(ans, right - left);
}
return ans;
}
};Java
import java.util.*;
class Solution {
public int longestSubarray(int[] nums) {
int left = 0, zeros = 0, ans = 0;
for (int right = 0; right < nums.length; right++) {
if (nums[right] == 0) zeros++;
while (zeros > 1) if (nums[left++] == 0) zeros--;
ans = Math.max(ans, right - left);
}
return ans;
}
}复杂度
时间
O(n)
左右指针各只前进一遍,每个元素进出窗口各一次
空间
O(1)
只用 left/zeros/ans 几个变量
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 删掉一个元素以后全为 1 的最长子数组 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
这道题和「最多翻 k 个 0 的最长连续 1(LC1004)」什么关系?+
是同一类滑动窗口:LC1004 允许窗口里最多 k 个 0、答案是窗口长度 right−left+1;本题相当于 k=1,但因为是「删除」而不是「翻转」,必须去掉一个元素,所以答案是 right−left(长度减一)。把 k 一般化、再注意删除与翻转的差别,两题就打通了。
为什么不用真的去删某个元素再算?+
不用。我们维护「最多含一个 0」的窗口,这个窗口删掉那个 0(或全 1 时删任一元素)后就是一段连续的 1,长度恰好 right−left。滑窗一遍就把所有候选窗口都覆盖了,不必真的去枚举删哪个。
想听吴师兄把这道题讲给你听？
文字版和动画都随便看。开通图解算法年卡，可以听吴师兄声线把 删掉一个元素以后全为 1 的最长子数组 一步步讲透（全站 0 节语音精讲，持续扩充）， 卡住的地方还有 AI 私教小欧就着动画帮你拆到懂。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。