Max Consecutive Ones III
題目描述
給定二進位陣列 nums 和整數 k，最多可以將 k 個 0 翻轉為 1，回傳翻轉後最長的連續 1 的長度。
輸入：nums = [1,1,1,0,0,0,1,1,1,1,0], k = 2
輸出：6（翻轉 nums[5] 和 nums[10]）
輸入：nums = [0,0,1,1,0,0,1,1,1,0,1,1,0,0,0,1,1,1,1], k = 3
輸出：10
解題思路
初始化
left = 0, zeroCount = 0, maxLen = 0。left 是窗口左邊界，zeroCount 追蹤窗口內 0 的個數
擴張右邊
right 用 for 迴圈從 0 到 n-1。若 nums[right] == 0 則 zeroCount++（消耗一次翻轉機會）
收縮左邊
while zeroCount > k：若 nums[left] == 0 則 zeroCount--（歸還翻轉機會），left++。直到窗口內 0 的個數 ≤ k
更新最大值
此時窗口 [left, right] 內最多 k 個 0，長度 = right - left + 1。用 maxLen 記錄歷史最大值
程式碼
C#
public class Solution {
public int LongestOnes(int[] nums, int k) {
int left = 0, zeroCount = 0, maxLen = 0;
for (int right = 0; right < nums.Length; right++) {
if (nums[right] == 0) zeroCount++;
// 窗口內 0 的數量超過 k，收縮左邊
while (zeroCount > k) {
if (nums[left] == 0) zeroCount--;
left++;
}
maxLen = Math.Max(maxLen, right - left + 1);
}
return maxLen;
}
}TypeScript
function longestOnes(nums: number[], k: number): number {
let left = 0, zeroCount = 0, maxLen = 0;
for (let right = 0; right < nums.length; right++) {
if (nums[right] === 0) zeroCount++;
while (zeroCount > k) {
if (nums[left] === 0) zeroCount--;
left++;
}
maxLen = Math.max(maxLen, right - left + 1);
}
return maxLen;
}Python
def longestOnes(nums: list[int], k: int) -> int:
left = zero_count = max_len = 0
for right in range(len(nums)):
if nums[right] == 0:
zero_count += 1
while zero_count > k:
if nums[left] == 0:
zero_count -= 1
left += 1
max_len = max(max_len, right - left + 1)
return max_len複雜度分析
| | Time | Space | |--|------|-------| | 本解法 | O(n) | O(1) |
right 從 0 走到 n-1 共 n 步，left 每步最多前進一格且不會後退，總共也最多走 n 步。兩個指針合計 ≤ 2n 步，因此時間 O(n)。只用三個整數變數，空間 O(1)。
邊界情況
- k = 0：不能翻轉任何 0，退化為找最長連續 1 的子陣列。窗口內不允許有 0
- 全部都是 1：例如
[1,1,1]，zeroCount 始終為 0，窗口擴到整個陣列，回傳 n - 全部都是 0：例如
[0,0,0]，k=2 時最多翻轉 2 個，最長為 min(n, k) = 2 - k ≥ 陣列中 0 的個數：可以翻轉所有 0，答案就是整個陣列長度 n
圖解
圖表展示窗口的擴張與收縮：right 持續擴張直到窗口內包含第 3 個 0（超過 k=2），此時 left 開始收縮直到吐出一個 0 讓 zeroCount 回到 2。最終最佳窗口為索引 5-10 的 [0,1,1,1,1,0]，長度 6。
進階觀點
💡面試追問
-
Q: while 換成 if 可以嗎？ A: 可以！因為每次 right 只加 1，zeroCount 最多超標 1（從 k 變成 k+1）。用 if 只收縮一次就夠了。這種寫法甚至讓窗口大小單調不減（只擴不縮），效果等價但邏輯更巧妙。
-
Q: k = 0 的特殊情況怎麼處理？ A: 不需要特殊處理。k=0 時，窗口內不允許有任何 0，遇到 0 就收縮。自然退化為找最長連續 1 的子陣列。
-
Q: 跟 LeetCode 1493（Longest Subarray of 1's After Deleting One Element）的關係？ A: 幾乎一樣的滑動窗口結構，但 1493 是「刪除一個元素」（必須刪，不能不刪），等價於「最多允許 1 個 0 在窗口中，但最終長度要減 1」。可以用本題的框架，k=1，最後答案減 1。
理解測驗
🤔 為什麼這是可變大小的滑動窗口？
🤔 nums = [0,0,0], k = 0 的結果是什麼？