MediumRating 1423
1493. Longest Subarray of 1's After Deleting One Element
sliding-windowarraydynamic-programming
解題說明
Longest Subarray of 1's After Deleting One Element
題目描述：給定一個二進位陣列 nums，你必須恰好刪除其中一個元素。請回傳刪除後子陣列中 1 的最長長度。若結果全為 1，則回傳 nums.length - 1。
解題思路：使用滑動視窗，維護一個最多包含一個 0 的視窗。用 left 和 right 兩個指標，計數視窗內 0 的個數 zeros。當 zeros > 1 時，將 left 右移直到移出一個 0。因為必須刪除一個元素，答案為視窗大小減一（right - left，不含被刪除的那個位置）。
C++ 解法
複雜度分析
時間複雜度：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，僅適合小規模輸入。
延伸思考
- 若允許刪除最多 k 個元素，最長全 1 子陣列應如何求？
- 若陣列不是二進位（元素為任意整數），改成刪除一個元素後最長非遞減子陣列，應如何解？
- 本題「必須恰好刪除一個元素」與「最多刪除一個元素」的答案會差多少？如何修改程式碼處理後者？