2163. Minimum Difference in Sums After Removal of Elements
解題說明
Minimum Difference in Sums After Removal of Elements
題目描述：給定長度為 3n 的整數陣列 nums。需移除恰好 n 個元素，使得前半部分（剩餘前 n 個中的最小 n 個之和）與後半部分（剩餘後 n 個中的最大 n 個之和）的差最小。回傳 sumFirst - sumSecond 的最小值。
解題思路：枚舉「分割點」k（從 n 到 2n），前 k 個元素中選最小的 n 個之和為 left[k]，後 3n-k 個元素中選最大的 n 個之和為 right[k]，答案為 min(left[k] - right[k]) 對所有有效 k 取最小。
預計算 left[]：用最大堆維護當前前綴中最小的 n 個數。從左向右掃描；若元素比堆頂小，替換堆頂並更新當前和。當前綴長度 ≥ n 時記錄 left[i]。
預計算 right[]：用最小堆維護當前後綴中最大的 n 個數，從右向左掃描，邏輯對稱。記錄 right[i]。
最後枚舉分割點 k（n ≤ k ≤ 2n），計算 left[k] - right[k] 的最小值。
C++ 解法
複雜度分析
時間複雜度：O(n log n) — 預計算 left[] 與 right[] 各需掃描 2n 個元素，每次堆操作為 O(log n)，最後枚舉分割點 O(n)，整體 O(n log n)。
空間複雜度：O(n) — 兩個堆各最多 n+1 個元素，left[] 與 right[] 陣列各長 3n，整體 O(n)。
虛擬碼
1. Set n = len(nums) / 3. 2. Compute left[] using max-heap (size capped at n): - Scan i from 0 to 2n-1; push nums[i]; if heap > n, pop max. - When heap size == n, record left[i] = current sum. 3. Compute right[] using min-heap (size capped at n): - Scan i from 3n-1 down to n; push nums[i]; if heap > n, pop min. - When heap size == n, record right[i] = current sum. 4. Initialize ans = LLONG_MAX. 5. For k from n to 2n: - ans = min(ans, left[k-1] - right[k]). 6. Return ans.
其他解法
方法一：排序 + 滑動視窗（僅適用特殊結構） 若陣列有特定結構（如已排序），可直接貪心選擇，無需動態維護堆。但一般情況下不適用，時間複雜度也無法優於 O(n log n)。
方法二：Segment Tree / Ordered Set
用有序集合（如 std::multiset）代替堆，支援 O(log n) 的插入與查詢第 n 小元素。邏輯相似，但常數較大，實作更複雜。適合需要支援刪除特定元素的變體問題。
方法三：暴力枚舉 對所有可能的移除方案暴力列舉，時間複雜度為 O(C(3n,n))，指數級，只適用於 n 極小（n ≤ 5）的情況，無法通過本題。
延伸思考
- 若移除元素數量不固定（例如移除 k 個，1 ≤ k ≤ n），如何修改算法以找到最優的 k？
- 本題的「維護前綴最小 n 個之和」子問題，在滑動視窗中位數（LeetCode 480）中也有類似結構，兩者有何異同？
- 若改為最大化
sumFirst - sumSecond（前大後小），算法需要做哪些對稱修改？