1004. 最大连续1的个数 III
题目描述
输入一个只含 0 和 1 的数组 nums，以及整数 k。
你最多可以把 k 个 0 改成 1。返回改完之后数组中最长一段连续 1 的长度。
示例 1
输入：nums = [1,1,1,0,0,0,1,1,1,1,0], k = 2 输出：6
解释：把下标 4、5 的两个 0 改成 1，得到下标 4 到 9 这段长度为 6 的全 1 段。
示例 2
输入：nums = [0,0,1,1,0,0,1,1,1,0,1,1,0,0,0,1,1,1,1], k = 3 输出：10
解释：把下标 4、5、9 的 0 改成 1，下标 2 到 11 连成长度 10 的全 1 段。
数据范围
1 <= nums.length <= 10^5nums[i]是0或1。0 <= k <= nums.length
解题思路：滑动窗口
问题等价于：找最长的子数组，其中 0 的个数不超过 k。用滑动窗口：右端逐个扩展并统计窗口内 0 的个数 zeros；一旦 zeros > k，就移动左端直到 zeros ≤ k。每个右端对应的合法窗口长度都参与更新答案。
为什么正确
每次更新答案时，窗口 [left, right] 内 0 的个数 ≤ k，且 left 是该右端能取的最小左端。
复杂度分析
时间 O(n)，左右指针都只右移；空间 O(1)。
易错点
收缩左端时只有移出的是 0 才把 zeros 减一；k = 0 时窗口只能包含 1。
参考代码
Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。
class Solution:
def longestOnes(self, nums: List[int], k: int) -> int:
left = zeros = ans = 0
for right, x in enumerate(nums):
if x == 0:
zeros += 1
while zeros > k:
if nums[left] == 0:
zeros -= 1
left += 1
ans = max(ans, right - left + 1)
return ansclass Solution {
public int longestOnes(int[] nums, int k) {
int left = 0, zeros = 0, ans = 0;
for (int right = 0; right < nums.length; right++) {
if (nums[right] == 0) {
zeros++;
}
while (zeros > k) {
if (nums[left] == 0) {
zeros--;
}
left++;
}
ans = Math.max(ans, right - left + 1);
}
return ans;
}
}class Solution {
public:
int longestOnes(vector<int>& nums, int k) {
int left = 0, zeros = 0, ans = 0;
for (int right = 0; right < (int)nums.size(); right++) {
if (nums[right] == 0) {
zeros++;
}
while (zeros > k) {
if (nums[left] == 0) {
zeros--;
}
left++;
}
ans = max(ans, right - left + 1);
}
return ans;
}
};func longestOnes(nums []int, k int) int {
left, zeros, ans := 0, 0, 0
for right, x := range nums {
if x == 0 {
zeros++
}
for zeros > k {
if nums[left] == 0 {
zeros--
}
left++
}
if right-left+1 > ans { ans = right - left + 1 }
}
return ans
}var longestOnes = function(nums, k) {
let left = 0, zeros = 0, ans = 0;
for (let right = 0; right < nums.length; right++) {
if (nums[right] === 0) {
zeros++;
}
while (zeros > k) {
if (nums[left] === 0) {
zeros--;
}
left++;
}
ans = Math.max(ans, right - left + 1);
}
return ans;
};function longestOnes(nums: number[], k: number): number {
let left = 0, zeros = 0, ans = 0;
for (let right = 0; right < nums.length; right++) {
if (nums[right] === 0) {
zeros++;
}
while (zeros > k) {
if (nums[left] === 0) {
zeros--;
}
left++;
}
ans = Math.max(ans, right - left + 1);
}
return ans;
}其他解法
两种方法都基于同一转化（区间内 0 的个数不超过 k）。二分法对每个右端点独立求最左端；滑动窗口利用左端点随右端点单调右移的性质，把二分省掉，达到线性时间。
解法 2：前缀和 + 二分查找 时间 O(n log n)，空间 O(n)
把题目转化为：找最长的区间，使其中 0 的个数不超过 k。用 pre[i] 记录前 i 个元素中 0 的个数，区间 [l, r] 中 0 的个数为 pre[r+1] - pre[l]。pre 单调不减，所以对每个右端点 r，可以二分出最小的 l 使 pre[r+1] - pre[l] ≤ k，用 r - l + 1 更新答案。
思路清晰，展示了“前缀和单调时可以二分”的通用技巧。比滑动窗口多一个 log 因子，并需要额外的前缀和数组。
class Solution:
def longestOnes(self, nums: List[int], k: int) -> int:
n = len(nums)
pre = [0] * (n + 1)
for i, x in enumerate(nums):
pre[i + 1] = pre[i] + (1 - x)
ans = 0
for right in range(n):
lo, hi = 0, right + 1
while lo < hi:
mid = (lo + hi) // 2
if pre[right + 1] - pre[mid] <= k:
hi = mid
else:
lo = mid + 1
ans = max(ans, right - lo + 1)
return ansclass Solution {
public int longestOnes(int[] nums, int k) {
int n = nums.length;
int[] pre = new int[n + 1];
for (int i = 0; i < n; i++) pre[i + 1] = pre[i] + (1 - nums[i]);
int ans = 0;
for (int right = 0; right < n; right++) {
int lo = 0, hi = right + 1;
while (lo < hi) {
int mid = (lo + hi) / 2;
if (pre[right + 1] - pre[mid] <= k) hi = mid;
else lo = mid + 1;
}
ans = Math.max(ans, right - lo + 1);
}
return ans;
}
}class Solution {
public:
int longestOnes(vector<int>& nums, int k) {
int n = nums.size();
vector<int> pre(n + 1, 0);
for (int i = 0; i < n; i++) pre[i + 1] = pre[i] + (1 - nums[i]);
int ans = 0;
for (int right = 0; right < n; right++) {
int lo = 0, hi = right + 1;
while (lo < hi) {
int mid = (lo + hi) / 2;
if (pre[right + 1] - pre[mid] <= k) hi = mid;
else lo = mid + 1;
}
ans = max(ans, right - lo + 1);
}
return ans;
}
};func longestOnes(nums []int, k int) int {
n := len(nums)
pre := make([]int, n+1)
for i, x := range nums {
pre[i+1] = pre[i] + 1 - x
}
ans := 0
for right := 0; right < n; right++ {
lo, hi := 0, right+1
for lo < hi {
mid := (lo + hi) / 2
if pre[right+1]-pre[mid] <= k {
hi = mid
} else {
lo = mid + 1
}
}
ans = max(ans, right-lo+1)
}
return ans
}var longestOnes = function(nums, k) {
const n = nums.length;
const pre = new Array(n + 1).fill(0);
for (let i = 0; i < n; i++) pre[i + 1] = pre[i] + (1 - nums[i]);
let ans = 0;
for (let right = 0; right < n; right++) {
let lo = 0, hi = right + 1;
while (lo < hi) {
const mid = (lo + hi) >> 1;
if (pre[right + 1] - pre[mid] <= k) hi = mid;
else lo = mid + 1;
}
ans = Math.max(ans, right - lo + 1);
}
return ans;
};function longestOnes(nums: number[], k: number): number {
const n = nums.length;
const pre = new Array<number>(n + 1).fill(0);
for (let i = 0; i < n; i++) pre[i + 1] = pre[i] + (1 - nums[i]);
let ans = 0;
for (let right = 0; right < n; right++) {
let lo = 0, hi = right + 1;
while (lo < hi) {
const mid = (lo + hi) >> 1;
if (pre[right + 1] - pre[mid] <= k) hi = mid;
else lo = mid + 1;
}
ans = Math.max(ans, right - lo + 1);
}
return ans;
}