LeetCode 1004: Max Consecutive Ones III

基本資料

#

難易度: medium 第一次嘗試： 2025-08-03

• 總花費時間：00:00.00

問題描述

#

給定一個二元陣列 nums 和一個整數 k，如果可以翻轉最多 k 個 0，則返回陣列中連續 1 的最大數量。這個問題本質上是要求包含最多 k 個零的最長子陣列。

解題思路

#

我們需要追蹤當前窗口中有多少個零。如果零的數量超過限制 k，我們就從左側開始縮小窗口，直到零的數量符合限制。這是一個經典的可變大小滑動窗口問題，我們可以盡可能地擴展窗口，並在必要時收縮窗口以維持約束條件。

解法

#

可變大小滑動窗口與零計數

#

class Solution:
    def longestOnes(self, nums: List[int], k: int) -> int:
        zero_count = max_len = left = 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

演算法分析

#

時間複雜度

#

• 時間: O(n)，其中 n 是輸入陣列的長度
• 空間: O(1)，因為我們只使用常數量的額外空間

關鍵洞察

#

1. 可變窗口大小: 與固定大小滑動窗口不同，這個窗口可以根據約束條件增長和縮小
2. 零計數: 我們只需要追蹤零的數量，而不是一的數量
3. 窗口縮小: 當約束條件被違反時，我們從左側縮小直到再次有效

收穫

#

1. 可變大小滑動窗口: 這道題展示了可變大小滑動窗口技巧，其中窗口大小可以根據約束條件（零的數量）改變。

2. 基於約束的窗口管理: 關鍵洞察是我們可以盡可能地擴展窗口，但當零的數量超過限制 k 時，我們必須縮小窗口。

3. 零計數策略: 我們只需要追蹤窗口中零的數量，而不是一的數量。這簡化了邏輯，因為我們本質上是在尋找包含最多 k 個零的最長子陣列。

4. 窗口縮小邏輯: 當零的數量超過 k 時，我們通過移動左指針從左側縮小窗口，直到零的數量回到限制之內。

5. 最大長度追蹤: 每當我們有一個有效窗口（零數量 ≤ k）時，我們持續更新最大長度。

6. 單次遍歷解決方案: 解決方案只需要遍歷陣列一次，對於大型輸入非常高效。

7. 記憶體效率: O(1) 空間複雜度使這個解決方案非常記憶體高效，因為我們只需要幾個變數來追蹤當前狀態。

8. 邊界情況處理: 解決方案自然地處理邊界情況，如全為一或全為零的陣列。

遇到的問題

#