What is the optimal approach for Max Consecutive Ones III?

Use a sliding window to count zeros and expand or shrink the window based on k flips allowed, ensuring the longest 1s sequence.

Can binary search be applied to Max Consecutive Ones III?

Yes, binary search over the possible window lengths combined with prefix sums can validate feasibility efficiently.

Why do we track zeros inside the window?

Tracking zeros ensures we do not exceed k flips, which is the key constraint for forming the maximum consecutive ones subarray.

What mistakes should be avoided when implementing this pattern?

Avoid flipping zeros that don't extend 1s sequences, mishandling window boundaries, or forgetting to update the max length after adjustment.

Does prefix sum improve performance in this problem?

Yes, prefix sums allow constant-time zero counts for any subarray, optimizing validation during sliding or binary search methods.

#1004

Medium

auto_awesome二分·搜索·答案·空间

LeetCode 题解工作台

最大连续1的个数 III

给定一个二进制数组 nums 和一个整数 k ，假设最多可以翻转 k 个 0 ，则返回执行操作后数组中连续 1 的最大个数。示例 1：输入： nums = [1,1,1,0,0,0,1,1,1,1,0], K = 2 输出： 6 解释： [1,1,1,0,0, 1 ,1,1,1,1, 1 ]…

数组二分查找滑动窗口前缀和

题目描述

给定一个二进制数组 nums 和一个整数 k，假设最多可以翻转 k 个 0 ，则返回执行操作后 数组中连续 1 的最大个数 。

示例 1：

输入：nums = [1,1,1,0,0,0,1,1,1,1,0], K = 2
输出：6
解释：[1,1,1,0,0,1,1,1,1,1,1]
粗体数字从 0 翻转到 1，最长的子数组长度为 6。

示例 2：

输入：nums = [0,0,1,1,0,0,1,1,1,0,1,1,0,0,0,1,1,1,1], K = 3
输出：10
解释：[0,0,1,1,1,1,1,1,1,1,1,1,0,0,0,1,1,1,1]
粗体数字从 0 翻转到 1，最长的子数组长度为 10。

提示：

1 <= nums.length <= 10⁵
nums[i] 不是 0 就是 1
0 <= k <= nums.length

lightbulb

解题思路

方法一：滑动窗口

我们可以遍历数组，用一个变量 $\textit{cnt}$ 记录当前窗口中 0 的个数，当 $\textit{cnt} > k$ 时，我们将窗口的左边界右移一位。

遍历结束后，窗口的长度即为最大连续 1 的个数。

注意，在上述过程中，我们不需要循环将窗口的左边界右移，而是直接将左边界右移一位，这是因为，题目求的是最大连续 1 的个数，因此，窗口的长度只会增加，不会减少，所以我们不需要循环右移左边界。

时间复杂度 $O(n)$ ，其中 $n$ 为数组的长度。空间复杂度 $O(1)$ 。

相似题目：

1

2

3

4

5

6

7

8

9

10

class Solution:
    def longestOnes(self, nums: List[int], k: int) -> int:
        l = cnt = 0
        for x in nums:
            cnt += x ^ 1
            if cnt > k:
                cnt -= nums[l] ^ 1
                l += 1
        return len(nums) - l

speed

复杂度分析

指标	值
时间	complexity is O(n) for sliding window, O(n log n) if using binary search over window size, and space complexity is O(1) for sliding window or O(n) for prefix sum. Each method aligns with the maximum-consecutive-ones pattern and handles large input efficiently.
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Focus on maximizing 1s using minimal zero flips.
question_mark
Consider the sliding window as the main pattern for handling consecutive sequences.
question_mark
Be aware of off-by-one errors when adjusting the window boundaries.

warning

常见陷阱

外企场景

error
Flipping zeros that do not extend a 1s sequence, wasting k flips.
error
Failing to shrink the window correctly when zero count exceeds k.
error
Incorrectly updating maximum length after window adjustment.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Return the subarray itself instead of its length.
arrow_right_alt
Allow flipping zeros with different weights or costs.
arrow_right_alt
Find maximum consecutive ones for multiple queries of k in the same array.

help

常见问题

外企场景

继续练习

#862 和至少为 K 的最短子数组 #713 乘积小于 K 的子数组 #1658 将 x 减到 0 的最小操作数