LeetCode 487. 最大连续1的个数 II
题目描述
给定一个二进制数组 nums，你可以将最多一个 0 变成 1。请返回经过替换后，数组中连续 1 的最大个数。
示例 1：
输入：nums = [1,0,1,1,0]
输出：4
解释：将下标 1 的 0 替换为 1 后，数组变为 [1,1,1,1,0]，最长连续 1 的个数为 4。
示例 2：
输入：nums = [0,0,1]
输出：2
解释：将下标 1 的 0 替换为 1 后，数组变为 [0,1,1]，最长连续 1 的个数为 2。
提示：
1 <= nums.length <= 10^5-
nums[i]为0或1。
题意分析
给定只包含零和一的数组，最多把一个零改成一，求能得到的最长连续一段的长度。可以不执行翻转，因此全为一时应返回整个数组长度。
一段区间能够通过这次操作变成全一，当且仅当它原来至多包含一个零。所以问题等价于寻找至多含一个零的最长连续子数组，不能跳过中间位置，也不需要真的修改输入。
解法：维护长度不缩小的滑动窗口
核心思路
[!blue]
代码维护一个长度不会缩小的窗口，窗口长度代表此前已经达到的最优值，窗口本身却不要求始终合法。
l是当前左边界，cnt记录当前窗口中的零数；二进制输入中x ^ 1在x = 0时为一，在x = 1时为零，可以直接用于增加或减少零计数。右端每读入一个元素，先把窗口临时扩长一位。若此时零数不超过一，这个更长的窗口合法，就把历史纪录提高一；若零数超过一，左端也前进一步，抵消刚增加的长度，让窗口退回旧纪录大小，而不是继续收缩到合法。
这种做法不会漏掉更优答案。设上一轮的最优长度为
best，新增一个元素后，任何更长的合法区间都必须以它为右端点；去掉这最后一位，仍是此前的合法区间，因此新纪录最多只能达到best + 1。刚扩张的窗口恰好就是这个长度的唯一候选，合法就增长，不合法就保持旧纪录，已经检查完本轮所有可能的改进。因此每轮结束时，窗口长度都等于已经扫描部分的最优答案。保持旧长度时，窗口可能仍含多个零，这只表示当前位置没有产生新纪录，不会否定此前已经存在的合法答案。随着左端继续移动，窗口以后仍可能恢复合法并再次增长。
最终右端已经扫描完数组，窗口长度就是
n - l，可以直接返回，不需要另存最大长度。这里的if与“始终保持合法”的while窗口是两种不同写法，不能只替换循环形式而仍沿用相同返回方式。
解题步骤
- 初始化左边界
l = 0、零数量cnt = 0。- 依次加入每个元素，用
x ^ 1更新零数量。- 若零数量超过一，减去即将移出的
nums[l]对零计数的贡献，并只让左边界前进一步。- 扫描结束后返回窗口最终长度
n - l。
代码实现
class Solution {
public int findMaxConsecutiveOnes(int[] nums) {
int l = 0;
int cnt = 0;
for (int x : nums) {
cnt += x ^ 1;
if (cnt > 1) {
cnt -= nums[l++] ^ 1;
}
}
return nums.length - l;
}
}
func findMaxConsecutiveOnes(nums []int) int {
l, cnt := 0, 0
for _, x := range nums {
cnt += x ^ 1
if cnt > 1 {
cnt -= nums[l] ^ 1
l++
}
}
return len(nums) - l
}
复杂度分析
- 时间复杂度：$O(n)$，右端扫描一次，每轮至多移动左端一步。
- 空间复杂度：$O(1)$ 额外空间。但本实现要回读
nums[l]，不能仅凭常数变量就认为它适合无法回读的输入流。
关键点总结
[!green]
- 窗口长度保存历史最优，当前窗口是否合法与历史答案是否存在不是同一件事。
- 每加入一位，最优长度最多增加一，只有这个更长候选值得检查。
- 超额时只移动左端一步保持旧纪录，因此最终长度直接等于答案。
解法二：两个后缀长度的流式递推
核心思路
[!blue]
若输入不能回读，可以只维护以当前元素结尾的两种最优长度：
plain是不含零的连续后缀长度，flex是至多含一个零的连续后缀长度。另用best保存所有结尾位置中的最大flex。新值为一时，两个后缀都可以直接向后延长一位。去掉新的一后，剩余部分仍必须是上一位置对应的合法后缀，因此在原最优长度上加一就是新最优。
新值为零时，不含零的后缀中断，
plain变为零。允许一个零的后缀必须把这次额度用在当前零上，前面的部分只能由连续一组成，所以新flex = 旧 plain + 1；此前含零的更长后缀不能再接上当前零。先使用旧
plain计算flex，再将plain清零，避免丢掉所需信息。每次更新后用flex更新best。整个过程只读取新到达的值，保留这三个状态就能持续处理数据流，不需要保存之前的元素；下方代码沿用题目的数组接口。
解题步骤
- 将
plain、flex、best初始化为零。- 读到一时，两种后缀长度都加一。
- 读到零时，先令
flex = plain + 1，再令plain = 0。- 更新
best，全部输入处理完后返回它；流式处理中也可以随时读取当前纪录。
代码实现
class Solution {
public int findMaxConsecutiveOnes(int[] nums) {
int plain = 0;
int flex = 0;
int best = 0;
for (int value : nums) {
if (value == 1) {
plain++;
flex++;
} else {
flex = plain + 1;
plain = 0;
}
best = Math.max(best, flex);
}
return best;
}
}
func findMaxConsecutiveOnes(nums []int) int {
plain, flex, best := 0, 0, 0
for _, value := range nums {
if value == 1 {
plain++
flex++
} else {
flex = plain + 1
plain = 0
}
if flex > best {
best = flex
}
}
return best
}
复杂度分析
- 时间复杂度：$O(n)$，每个输入值只做一次常数时间的状态转移。
- 空间复杂度：$O(1)$，只保留三个长度，不保存历史输入或回读旧位置。
关键点总结
[!green]
- 以当前位置结尾的后缀状态，让新元素能通过固定规则接入。
- 当前为零时，允许一次翻转的后缀只能接在此前纯一后缀之后。
flex可能下降，best才是全部已读输入中的最长答案。
易错点总结
[!yellow]
- 把最多翻转一次理解成必须翻转，会错误处理全为一的数组。
- 看到最终窗口仍不合法，就认定返回长度错误；该长度可能在更早位置由合法窗口取得。
- 改成
while收缩到合法后仍只返回最终窗口长度，会丢掉更早出现过的较长窗口，应另存最大值。- 只递增左边界而不更新移出元素的零计数，会使后续状态与实际窗口脱节。
- 数据流中不能回读左端元素时，直接照搬原窗口代码会缺少被移出值的信息。
- 后缀递推方法只返回最后的后缀长度，也会漏掉较早结束的最佳区间，需要保留历史最大值。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 1004. 最大连续1的个数 III | 中等 | 把允许翻转次数从 1 改为 k，窗口约束相应变为零的数量不超过 k。 |
| 1493. 删掉一个元素以后全为 1 的最长子数组 | 中等 | 原题必须删除一个位置，即使全为 1 也要扣除一位，本题允许不操作。 |