題目
給定一個二進制數組 nums 和一個整數 k，假設最多可以翻轉 k 個 0 ，則返回執行操作后 數組中連續 1 的最大個數 。
一、代碼實現
func longestOnes(nums []int, k int) int {left, zeroCnt, maxLen := 0, 0, 0for right := 0; right < len(nums); right++ {if nums[right] == 0 {zeroCnt++}// 窗口收縮條件for zeroCnt > k {if nums[left] == 0 {zeroCnt--}left++}// 更新最大窗口長度maxLen = max(maxLen, right - left + 1)}return maxLen
}func max(a, b int) int {if a > b { return a }return b
}
二、算法分析
1. 核心思路
- 滑動窗口機制：維護一個允許最多包含
k個 0 的窗口，通過動態調整左右邊界尋找最大連續 1 的區間 - 貪心策略：當窗口內 0 的數量超過
k時，左邊界右移直到滿足條件，確保窗口始終包含有效解
2. 關鍵步驟
- 初始化窗口：左邊界
left=0，統計窗口內 0 的數量zeroCnt - 擴展右邊界：遍歷數組元素，遇到 0 時增加計數
- 收縮條件：當
zeroCnt > k時，左移左邊界并更新計數 - 極值記錄：每次循環記錄窗口最大長度
3. 復雜度分析
| 指標 | 值 | 說明 |
|---|---|---|
| 時間復雜度 | O(n) | 每個元素最多被訪問兩次（左右指針各一次） |
| 空間復雜度 | O(1) | 僅需存儲指針和計數器變量 |
三、圖解示例
四、邊界條件與擴展
1. 特殊場景處理
- 全1數組：
nums = [1,1,1], k=0→ 直接返回數組長度 - k=0情況：等價于尋找最長連續1的子數組
- 超大k值：當
k ≥ 數組0的總數時返回數組長度
2. 多語言實現對比
| 語言 | 實現要點 | 性能優化技巧 |
|---|---|---|
| Python | 使用collections.deque記錄0的位置 | 預計算0的索引數組加速窗口調整 |
| Java | ArrayDeque存儲0的索引，窗口調整時直接跳轉到首個無效位置后 | 位運算優化0計數邏輯 |
| C++ | 雙指針配合zero_count變量，無需額外存儲結構 | 循環展開優化邊界判斷 |
3. 算法對比
| 方法 | 優點 | 缺點 |
|---|---|---|
| 滑動窗口法 | 時間復雜度最優，空間效率高 | 需處理指針同步邏輯 |
| 前綴和+二分 | 支持隨機查詢 | 空間復雜度O(n) |
| 暴力枚舉 | 實現簡單 | 時間復雜度O(n2) |
五、總結與拓展
1. 核心創新點
- 窗口動態調整：通過
zeroCnt計數器的狀態機式管理，實現線性時間復雜度 - 無效位置跳躍：當窗口收縮時，左指針可直接跳轉到首個無效0的后一位，減少冗余計算
2. 數學證明
設數組長度為 n，窗口左右指針移動總距離為 2n，算法時間復雜度嚴格為 O(n)。通過歸納法可證：每次窗口擴展必然覆蓋當前最優解的可能性，收縮操作確保不遺漏更優解。
3. 應用場景擴展
- 網絡質量監測：統計允許丟包情況下的最大連續正常信號段
- DNA序列分析：查找允許突變次數內的最長保守序列
- 用戶行為分析：檢測連續活躍天數（允許短暫中斷）
---損失(loss) 準確率(accuracy)問題)
)
)
