題目資訊

• 題目編號: 487
• 題目連結: Max Consecutive Ones II
• 主題: Array, Dynamic Programming, Sliding Window

題目敘述

給定一個二進制陣列 nums，返回陣列中連續1的最大個數，條件是你最多可以翻轉一個0。

範例 1:

輸入: nums = [1,0,1,1,0]
輸出: 4
解釋:

• 如果我們翻轉第一個0，nums 變為 [1,1,1,1,0]，我們得到4個連續的1。
• 如果我們翻轉第二個0，nums 變為 [1,0,1,1,1]，我們得到3個連續的1。
• 連續1的最大個數是 4。

範例 2:

輸入: nums = [1,0,1,1,0,1]
輸出: 4
解釋:

• 如果我們翻轉第一個0，nums 變為 [1,1,1,1,0,1]，我們得到4個連續的1。
• 如果我們翻轉第二個0，nums 變為 [1,0,1,1,1,1]，我們得到4個連續的1。
• 連續1的最大個數是 4。

約束條件：

• $1 \leq \text{nums.length} \leq 10^5$
• $\text{nums}[i]$ 要麼是 0，要麼是 1。

進一步思考

如果輸入的數字是一個無限流，即數字一個接一個來而且因為太大無法完整儲存在內存中，你如何高效地解決這個問題？

直覺

此問題要求我們在一個二元陣列中找到最多的連續 1，而我們可以將最多一個 0 翻轉為 1。挑戰在於有效地跟蹤連續 1 的最長序列，同時考慮翻轉一個 0 的可能性。解決方案需要在維持當前 1 序列時，找到一個最佳時機來翻轉一個 0。滑動窗口技術非常適合此問題，因為它允許我們動態調整窗口的邊界，同時遵循至多翻轉一個 0 的限制條件。

解法

此解法使用滑動窗口技術，兩個指針 left 和 right 用於標示當前檢查窗口在給定二元陣列 nums 中的邊界。演算法使用變量 zeroCount 來計算當前滑動窗口中的 0 的數量，目標是達到翻轉不超過一個 0 的條件。

1. 初始化 left 和 right 指針為位置 0，zeroCount 為 0，maxConsecutive 為 0。這些變量將用來追蹤當前窗口的邊界，窗口中的 0 的數量，以及找到的最多連續 1 的長度。

2. 使用 right 指針遍歷陣列：

   • 當遇到 0（即 nums[right] 不是 1）時，評估 zeroCount：
     • 如果 zeroCount 是 0，這是我們第一次要翻轉的 0，因此增量 zeroCount 以標示該翻轉的 0。
     • 如果 zeroCount 已經是 1，意味著我們之前已經翻轉過一個 0，則移動 left 指針以減少 0 的數量。增量 left 直到窗口內的一個 0 被有效移除，此操作將窗口設置到一個狀態，就像我們正在考慮翻轉這個新的 0。

3. 在每次迭代步驟中，通過評估當前窗口大小 right - left + 1 計算潛在的最多連續 1，並使用 maxConsecutive 變量保持全域最大值。

4. 持續此過程直到 right 指針將整個陣列評估完畢，並更新 maxConsecutive 以反映最大可能達到的連續 1 的序列。

5. 迭代結束後，maxConsecutive 會持有結果，這應當被作為最終答案返回。

通過有效地管理窗口大小和只翻轉一個 0，此演算法在翻轉的策略選擇和窗口大小最大化之間實現了最優平衡，並在線性時間複雜度的限制下提供了一個有效的解決方案。

程式碼

C++

class Solution {
public:
    int findMaxConsecutiveOnes(vector<int>& nums) {
        int left = 0, right = 0;  // 滑動視窗的指標
        int zeroCount = 0;        // 視窗內0的計數器
        int maxConsecutive = 0;   // 最大連續1的個數

        // 使用右指標遍歷nums數組
        for (; right < nums.size(); right++) {
            // 如果當前數字不是1，那就是0
            if (nums[right] != 1) {
                // 如果是遇到的第一個0，則增加zeroCount
                if (zeroCount == 0) {
                    zeroCount = 1;
                } else {
                    // 否則，移動左指標以減少0的計數
                    while (nums[left++] == 1) {}
                }
            }
            // 計算遇到的最大視窗大小
            maxConsecutive = max(maxConsecutive, right - left + 1);
        }
        return maxConsecutive;
    }
};

Python

class Solution:
    def findMaxConsecutiveOnes(self, nums):
        left, right = 0, 0  # 用於滑動窗口的指針
        zeroCount = 0       # 計數窗口內的零
        maxConsecutive = 0  # 最大的連續1的數量

        # 使用右指針遍歷nums數組
        for right in range(len(nums)):
            # 如果當前數字不是1，那就是0
            if nums[right] != 1:
                # 如果這是遇到的第一個零，增加zeroCount
                if zeroCount == 0:
                    zeroCount = 1
                else:
                    # 否則，移動左指針以減少零的計數
                    while nums[left] == 1:
                        left += 1
                    left += 1
            # 計算遇到的最大窗口大小
            maxConsecutive = max(maxConsecutive, right - left + 1)

        return maxConsecutive

複雜度分析

• 時間複雜度: $O(n)$

  該演算法使用滑動窗口技術，其中 left 和 right 指針遍歷數組 nums。right 指針每次向前移動一個步驟，而 left 指針可能會在必要時向前移動，以確保窗口內最多只有一個零。數組中的每個元素最多被處理兩次（一次由 right，可能還有一次由 left），因此時間複雜度為 $O(n)$，其中 $n$ 是數組 nums 的長度。

• 空間複雜度: $O(1)$

  該演算法使用恆定數量的額外空間，因為它只維護固定數量的變量（left，right，zeroCount 和 maxConsecutive），而不受輸入數組大小的影響。因此，空間複雜度是 $O(1)$。