LeetCode中國站原文

https://leetcode.cn/problems/minimum-difference-in-sums-after-removal-of-elements/

原始題目

題目描述

給你一個下標從 0 開始的整數數組 nums ，它包含 3 * n 個元素。

你可以從 nums 中刪除 恰好 n 個元素，剩下的 2 * n 個元素將會被分成兩個 相同大小 的部分。

• 前面 n 個元素屬于第一部分，它們的和記為 sumfirst 。
• 后面 n 個元素屬于第二部分，它們的和記為 sumsecond 。

兩部分和的 差值 記為 sumfirst - sumsecond 。

請你返回刪除 n 個元素之后，剩下兩部分和的 差值的最小值 是多少。

示例 1：

輸入：nums =
輸出：-1
解釋：n = 1。刪除 nums = 3，數組變為 。差值為 1 - 2 = -1。

示例 2：

輸入：nums =
輸出：1
解釋：n = 2。刪除 nums = 9 和 nums = 1，剩下 。差值為 (7+5) - (8+3) = 1。

提示：

• $nums.length==3?n$
• $1<=n<=10^5$
• $1<=nums[i]<=10^5$

講解

分割線的藝術：前后綴分解與優先隊列的完美邂逅

大家好！今天我們要拆解的，是一道極具思維含量與工程美感的題目——LeetCode 2163. 刪除元素后和的最小差值。

這道題的目標是最小化 sumfirst - sumsecond。要達到這個目的，我們的策略必須是雙管齊下：

1. 讓 sumfirst 盡可能小。
2. 讓 sumsecond 盡可能大。

但問題在于，我們刪除的 n 個元素會同時影響這兩個部分的選擇，如何找到那個最佳的平衡點呢？答案就藏在“分割線”的移動之中。

第一部分：算法思想 —— “分割線”與前后綴分解

1. 想象一條看不見的“分割線”

我們最終要留下 2n 個元素，前 n 個歸第一部分，后 n 個歸第二部分。這 2n 個元素在原數組 nums 中保持著它們的相對順序。

我們可以想象，在原數組 nums 中，存在一條看不見的**“分割線”，它將 nums 分成了前后兩個部分：一個前綴和一個后綴**。

• sumfirst 的 n 個元素，全部來自于這條分割線左邊的前綴。
• sumsecond 的 n 個元素，全部來自于這條分割線右邊的后綴。

分割線可以放在哪里？

• 為了能從前綴中選出 n 個數，前綴的長度至少為 n。所以分割線最早可以在索引 n-1 之后。
• 為了能從后綴中選出 n 個數，后綴的長度至少為 n。所以分割線最晚可以在索引 2n-1 之后。

我們的核心思路就是：遍歷所有可能的分割線位置，對于每一個位置，都計算出最優的 sumfirst - sumsecond，然后取其中的最小值。

2. 前后綴分解：預計算的威力

如果每次移動分割線，我們都重新計算前綴的最小和與后綴的最大和，那效率太低了。解決這個問題的鑰匙，就是**“前后綴分解”**——提前把所有可能需要的信息都算好。

我們需要兩個“信息表”：

1. prefixMinSum[i]：存儲 nums[0...i] 這個前綴中，最小的 n 個元素之和。
2. suffixMaxSum[i]：存儲 nums[i...3n-1] 這個后綴中，最大的 n 個元素之和。

只要我們能高效地構建出這兩個表，問題就迎刃而解了。

第二部分：實現工具 —— 優先隊列（堆）

如何高效地“在一堆動態變化的數中，維護前K大/小的元素之和”？這正是優先隊列（Priority Queue，即堆） 的拿手好戲。

1. 計算 prefixMinSum (前綴最小和)

我們需要一個大頂堆 (Max-Heap)，它的作用像一個“VIP室”，容量只有 n。

1. 我們從左到右遍歷 nums。
2. 每遇到一個數，都讓它嘗試進入“VIP室”。
3. 如果“VIP室”還沒滿（不足n人），新來的數直接進入。
4. 如果“VIP室”滿了，新來的數就要和室內的“最大塊頭”（堆頂元素）比一下。如果新來的數比它小，說明新來的更“VIP”（因為我們要找最小的），就把那個“最大塊頭”請出去，讓新來的數進來。
5. 我們始終維護“VIP室”內所有數的總和。當遍歷到索引 i 時，這個總和就是 nums[0...i] 中最小的 n 個元素之和。

flowchart TDA[初始化一個大小為 n 的<b>大頂堆</b> 和 sum=0] --> B{從左到右遍歷 nums};B --> C{將 nums[i] 加入堆和 sum};C --> D{堆的大小是否 > n?};D -- 是 --> E[sum -= 堆頂元素<br>從堆中移除堆頂元素];D -- 否 --> F;E --> F;F --> G{i 是否 >= n-1?};G -- 是 --> H[記錄 prefixMinSum[i] = sum];G -- 否 --> B;H --> B;

2. 計算 suffixMaxSum (后綴最大和)

這個過程完全對稱。我們需要一個小頂堆 (Min-Heap)，容量同樣為 n。

1. 我們從右到左遍歷 nums。
2. 每遇到一個數，讓它和“VIP室”里的“最小塊頭”（堆頂元素）比。如果新來的數比它大，就請“最小塊頭”出去，讓新來的進來。
3. 這樣，我們就能始終維護后綴中最大的 n 個元素之和。

第三部分：代碼實現 —— 組裝最終答案

有了預計算好的 prefixMinSum 和 suffixMaxSum 數組，最后的組裝就非常簡單了。

import java.util.PriorityQueue;
import java.util.Collections;public class Solution {public long minimumDifference(int[] nums) {int n = nums.length / 3;// ======================= 步驟 1: 計算前綴最小和 =======================// prefixMinSum[i] = nums[0...i] 中，n個最小元素的和long[] prefixMinSum = new long[3 * n];// 使用大頂堆來動態維護n個最小的元素PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());long currentSum = 0;for (int i = 0; i < 3 * n; i++) {currentSum += nums[i];maxHeap.add(nums[i]);if (maxHeap.size() > n) {currentSum -= maxHeap.poll(); // 移除最大的那個}if (maxHeap.size() == n) {prefixMinSum[i] = currentSum;}}// ======================= 步驟 2: 計算后綴最大和 =======================// suffixMaxSum[i] = nums[i...3n-1] 中，n個最大元素的和long[] suffixMaxSum = new long[3 * n];// 使用小頂堆來動態維護n個最大的元素PriorityQueue<Integer> minHeap = new PriorityQueue<>();currentSum = 0;for (int i = 3 * n - 1; i >= 0; i--) {currentSum += nums[i];minHeap.add(nums[i]);if (minHeap.size() > n) {currentSum -= minHeap.poll(); // 移除最小的那個}if (minHeap.size() == n) {suffixMaxSum[i] = currentSum;}}// ======================= 步驟 3: 遍歷分割點，尋找最小差值 =======================long minDifference = Long.MAX_VALUE;// 分割線在索引 i 和 i+1 之間// i 的范圍是從 n-1 到 2n-1for (int i = n - 1; i < 2 * n; i++) {long sumFirst = prefixMinSum[i];       // 前綴 nums[0...i] 的最小n和long sumSecond = suffixMaxSum[i + 1];  // 后綴 nums[i+1...3n-1] 的最大n和minDifference = Math.min(minDifference, sumFirst - sumSecond);}return minDifference;}
}

代碼精講

1. 數據類型：由于數字和 n 的范圍較大，和可能會超出 int 的范圍，因此我們全程使用 long 來存儲和，避免溢出。
2. 大頂堆的創建：Java的 PriorityQueue 默認是小頂堆，創建大頂堆需要傳入 Collections.reverseOrder()。
3. 循環范圍：計算前綴和后綴的循環覆蓋了整個數組。但最后尋找答案的循環，分割點 i 的范圍是從 n-1 到 2*n-1（注意不是 < 2*n），這保證了前綴和后綴都有至少 n 個元素可供選擇。

通過這“三步走”戰略，我們把一個復雜的、看似需要回溯搜索的問題，轉化成了一個結構清晰、邏輯流暢的動態規劃+數據結構優化問題。