題目描述:給定一個二進位陣列 nums,你必須恰好刪除其中一個元素。請回傳刪除後子陣列中 1 的最長長度。若結果全為 1,則回傳 nums.length - 1。
解題思路:使用滑動視窗,維護一個最多包含一個 0 的視窗。用 left 和 right 兩個指標,計數視窗內 0 的個數 zeros。當 zeros > 1 時,將 left 右移直到移出一個 0。因為必須刪除一個元素,答案為視窗大小減一(right - left,不含被刪除的那個位置)。
時間複雜度:O(n) — left 和 right 各最多移動 n 步。
空間複雜度:O(1) — 只使用常數額外空間。
1. Initialize left = 0, zeros = 0, ans = 0
2. For right from 0 to n-1:
a. If nums[right] == 0, increment zeros
b. While zeros > 1:
- If nums[left] == 0, decrement zeros
- left++
c. Update ans = max(ans, right - left) // window size minus the deleted slot
3. Return ans動態規劃 O(n):dp0[i] 表示以 i 結尾、尚未刪除任何元素的最長連續 1 長度;dp1[i] 表示已刪除一個元素的最長連續 1 長度。轉移:若 nums[i]==1,dp0[i]=dp0[i-1]+1,dp1[i]=dp1[i-1]+1;若 nums[i]==0,dp0[i]=0,dp1[i]=dp0[i-1]。最終取 max(dp1) — 與滑動視窗等效但程式碼稍長。
暴力法 O(n²):枚舉每個刪除位置,計算剩餘陣列中最長的連續 1,僅適合小規模輸入。