題目描述:給定二元陣列 nums 和整數 k,最多可以將 k 個 0 翻轉成 1,回傳能得到的最長連續 1 的子陣列長度。
解題思路:使用滑動視窗。問題等價於:找出最多含 k 個 0 的最長子陣列。維護左指針 left、右指針 right 以及視窗內 0 的個數 zerosInWindow。右指針向右擴展時,若 nums[right] == 0 則增加 zerosInWindow。每當 zerosInWindow > k,從左側收縮:若 nums[left] == 0 則減少 zerosInWindow,然後右移 left,直到 zerosInWindow <= k。視窗合法後,以 right - left + 1 更新最大長度。因為每個元素至多被加入和移除一次,整體為 O(n)。若 k >= n,則整個陣列都可翻轉,直接回傳 n(不過正常流程也能正確處理此情況)。
時間複雜度:O(n) — right 和 left 各最多移動 n 次,每步操作為 O(1),整體 O(n)。
空間複雜度:O(1) — 只使用常數個輔助變數,不需要額外陣列。
1. Initialize left = 0, maxLen = 0, zerosInWindow = 0.
2. For right from 0 to n-1:
a. If nums[right] == 0, increment zerosInWindow.
b. While zerosInWindow > k:
- If nums[left] == 0, decrement zerosInWindow.
- Increment left.
c. Update maxLen = max(maxLen, right - left + 1).
3. Return maxLen.方法一:滑動視窗(最優解) — 如本題解,時間 O(n)、空間 O(1)。以「視窗內 0 的個數不超過 k」為合法條件,直接求最長視窗。
方法二:前綴和 + 二分搜尋 — 建立 0 的位置陣列 zeroPos,對每個右端點 r,二分搜尋找最左的左端點使得區間內 0 的個數不超過 k。時間 O(n log n)、空間 O(n)。思路清晰,適合需要找具體翻轉位置的變形題。
方法三:不縮小視窗的滑動視窗變體 — 使視窗只增不減(當 zerosInWindow > k 時移動 left 一步而不用 while),這樣 right - left 始終代表歷史最大長度。時間 O(n)、空間 O(1),且程式碼更簡潔;但會使得 left 不一定指向最優左端點,需理解其正確性。
right - left 仍能給出正確的最大長度?能否用數學歸納法證明?