LeetCode 1004: Max Consecutive Ones III (Sliding Window with Flip Budget)
LeetCode 1004Sliding WindowTwo PointersToday we solve LeetCode 1004 - Max Consecutive Ones III.
Source: https://leetcode.com/problems/max-consecutive-ones-iii/
English
Problem Summary
Given a binary array nums and an integer k, you may flip at most k zeros into ones. Return the maximum number of consecutive ones possible.
Key Insight
Maintain a window [left, right] that contains at most k zeros. If zeros exceed k, move left rightward until the window becomes valid again. The answer is the largest valid window length.
Brute Force and Limitations
Brute force checks every subarray and counts zeros, costing O(n^2) (or O(n^3) if counting each time). This is too slow for large input sizes.
Optimal Algorithm Steps (Sliding Window)
1) Initialize left = 0, zeroCount = 0, best = 0.
2) Expand right from 0 to n-1; if nums[right] == 0, increment zeroCount.
3) While zeroCount > k, shrink from left; if leaving element is 0, decrement zeroCount.
4) Update best = max(best, right - left + 1).
Complexity Analysis
Time: O(n), each pointer moves at most n times.
Space: O(1).
Common Pitfalls
- Forgetting to decrement zeroCount when left passes a zero.
- Using if instead of while for shrinking when multiple extra zeros exist.
- Updating answer before restoring window validity.
Reference Implementations (Java / Go / C++ / Python / JavaScript)
class Solution {
public int longestOnes(int[] nums, int k) {
int left = 0, zeroCount = 0, best = 0;
for (int right = 0; right < nums.length; right++) {
if (nums[right] == 0) zeroCount++;
while (zeroCount > k) {
if (nums[left] == 0) zeroCount--;
left++;
}
best = Math.max(best, right - left + 1);
}
return best;
}
}func longestOnes(nums []int, k int) int {
left, zeroCount, best := 0, 0, 0
for right := 0; right < len(nums); right++ {
if nums[right] == 0 {
zeroCount++
}
for zeroCount > k {
if nums[left] == 0 {
zeroCount--
}
left++
}
if right-left+1 > best {
best = right - left + 1
}
}
return best
}class Solution {
public:
int longestOnes(vector<int>& nums, int k) {
int left = 0, zeroCount = 0, best = 0;
for (int right = 0; right < (int)nums.size(); ++right) {
if (nums[right] == 0) zeroCount++;
while (zeroCount > k) {
if (nums[left] == 0) zeroCount--;
left++;
}
best = max(best, right - left + 1);
}
return best;
}
};class Solution:
def longestOnes(self, nums: List[int], k: int) -> int:
left = 0
zero_count = 0
best = 0
for right, value in enumerate(nums):
if value == 0:
zero_count += 1
while zero_count > k:
if nums[left] == 0:
zero_count -= 1
left += 1
best = max(best, right - left + 1)
return best/**
* @param {number[]} nums
* @param {number} k
* @return {number}
*/
var longestOnes = function(nums, k) {
let left = 0, zeroCount = 0, best = 0;
for (let right = 0; right < nums.length; right++) {
if (nums[right] === 0) zeroCount++;
while (zeroCount > k) {
if (nums[left] === 0) zeroCount--;
left++;
}
best = Math.max(best, right - left + 1);
}
return best;
};中文
题目概述
给定二进制数组 nums 和整数 k，你最多可以把 k 个 0 翻转成 1。求最长连续 1 的长度。
核心思路
维护一个滑动窗口 [left, right]，保证窗口内 0 的个数不超过 k。当 0 的个数超标时，不断右移左指针直到窗口重新合法。所有合法窗口中的最大长度即答案。
基线解法与不足
暴力解会枚举所有子数组并统计 0 的数量，复杂度至少 O(n^2)，在大输入下会超时。
最优算法步骤（滑动窗口）
1）初始化 left = 0、zeroCount = 0、best = 0。
2）右指针逐步扩展，遇到 0 就增加 zeroCount。
3）若 zeroCount > k，持续右移左指针；若移出的是 0 则减少计数。
4）每轮更新最大窗口长度 best。
复杂度分析
时间复杂度：O(n)。
空间复杂度：O(1)。
常见陷阱
- 左指针越过 0 后忘记减少 zeroCount。
- 超标时只收缩一次（if）而不是循环收缩（while）。
- 在窗口仍非法时就更新答案。
多语言参考实现（Java / Go / C++ / Python / JavaScript）
class Solution {
public int longestOnes(int[] nums, int k) {
int left = 0, zeroCount = 0, best = 0;
for (int right = 0; right < nums.length; right++) {
if (nums[right] == 0) zeroCount++;
while (zeroCount > k) {
if (nums[left] == 0) zeroCount--;
left++;
}
best = Math.max(best, right - left + 1);
}
return best;
}
}func longestOnes(nums []int, k int) int {
left, zeroCount, best := 0, 0, 0
for right := 0; right < len(nums); right++ {
if nums[right] == 0 {
zeroCount++
}
for zeroCount > k {
if nums[left] == 0 {
zeroCount--
}
left++
}
if right-left+1 > best {
best = right - left + 1
}
}
return best
}class Solution {
public:
int longestOnes(vector<int>& nums, int k) {
int left = 0, zeroCount = 0, best = 0;
for (int right = 0; right < (int)nums.size(); ++right) {
if (nums[right] == 0) zeroCount++;
while (zeroCount > k) {
if (nums[left] == 0) zeroCount--;
left++;
}
best = max(best, right - left + 1);
}
return best;
}
};class Solution:
def longestOnes(self, nums: List[int], k: int) -> int:
left = 0
zero_count = 0
best = 0
for right, value in enumerate(nums):
if value == 0:
zero_count += 1
while zero_count > k:
if nums[left] == 0:
zero_count -= 1
left += 1
best = max(best, right - left + 1)
return best/**
* @param {number[]} nums
* @param {number} k
* @return {number}
*/
var longestOnes = function(nums, k) {
let left = 0, zeroCount = 0, best = 0;
for (let right = 0; right < nums.length; right++) {
if (nums[right] === 0) zeroCount++;
while (zeroCount > k) {
if (nums[left] === 0) zeroCount--;
left++;
}
best = Math.max(best, right - left + 1);
}
return best;
};
Comments