这道题实际上是 LeetCode 2163. 删除元素后和的最小差值Minimum Difference in Sums After Removal of Elements。LintCode 3877 应该是该题的复刻或类似编号。题目大意给定一个包含 3n 个整数的数组 nums。你需要从中删除恰好 n 个元素使得剩下的 2n 个元素被分成两部分前 n 个元素属于第一部分和为 sum_{first}。后 n 个元素属于第二部分和为 sum_{second}。目标是最小化差值 sum_{first} - sum_{second}。解题思路这是一个经典的贪心 优先队列堆问题。分割点枚举删除 n 个元素后剩下的 2n 个元素在原数组中是连续的吗不是。但是我们可以想象在原始数组中找到一个分割点 in le i le 2n使得第一部分从 nums[0…i-1] 中选出最小的 n 个数。第二部分从 nums[i…3n-1] 中选出最大的 n 个数。为什么是这样为了让 sum_{first} - sum_{second} 最小我们需要 sum_{first} 尽可能小sum_{second} 尽可能大。第一部分必须取自分割点左侧的某个子集且为了最小化和我们肯定选左侧最小的 n 个。第二部分必须取自分割点右侧的某个子集且为了最大化和我们肯定选右侧最大的 n 个。分割点 i 的范围左边至少要留 n 个元素供选择所以 i ge n右边至少要留 n 个元素供选择所以 i le 2n。预处理后缀最大值和我们需要快速知道对于任意分割点 i右侧 nums[i…3n-1] 中最大的 n 个数之和。从右向左遍历维护一个最小堆大小为 n。堆中保存当前遇到的最大的 n 个数。当新元素大于堆顶时弹出堆顶压入新元素并更新和。记录每个位置 i 对应的最大 n 个数之和存入数组 sufMax[i]。计算前缀最小值和并更新答案从左向右遍历维护一个最大堆大小为 n。堆中保存当前遇到的最小的 n 个数。当新元素小于堆顶时弹出堆顶压入新元素并更新和。当遍历到位置 i作为分割点此时左边有 i 个元素即 0 到 i-1如果 i ge n则计算当前的 sum_{first} - sufMax[i]并更新全局最小值。复杂度分析时间复杂度O(N log N)其中 N 是数组长度这里 N3n。我们需要遍历数组两次每次操作堆的复杂度是 log n。空间复杂度O(N)用于存储后缀和数组以及堆。Java 代码实现import java.util.PriorityQueue;public class Solution {public long minimumDifference(int[] nums) {int m nums.length;int n m / 3;// sufMax[i] 表示从 nums[i...m-1] 中选出的最大的 n 个数的和 long[] sufMax new long[m 1]; // 1. 从右向左处理计算后缀最大 n 个数之和 // 使用最小堆来维护最大的 n 个数堆顶是当前 n 个数中最小的容易被替换 PriorityQueue minHeap new PriorityQueue(); long currentSum 0; // 初始化先放入最后 n 个元素 for (int i m - 1; i m - n; i--) { minHeap.offer(nums[i]); currentSum nums[i]; } sufMax[m - n] currentSum; // 继续向左遍历更新堆和和 for (int i m - n - 1; i n; i--) { if (nums[i] minHeap.peek()) { int removed minHeap.poll(); minHeap.offer(nums[i]); currentSum currentSum - removed nums[i]; } sufMax[i] currentSum; } // 2. 从左向右处理计算前缀最小 n 个数之和并同时计算答案 // 使用最大堆来维护最小的 n 个数堆顶是当前 n 个数中最大的容易被替换 PriorityQueue maxHeap new PriorityQueue((a, b) - b - a); currentSum 0; // 初始化先放入前 n 个元素 for (int i 0; i n; i) { maxHeap.offer(nums[i]); currentSum nums[i]; } // 初始答案分割点在 n 处 long ans currentSum - sufMax[n]; // 继续向右遍历更新堆和和并尝试更新答案 // 分割点 i 表示左边取 [0, i-1]右边取 [i, m-1] // i 的范围从 n1 到 2n for (int i n; i 2 * n; i) { if (nums[i] maxHeap.peek()) { int removed maxHeap.poll(); maxHeap.offer(nums[i]); currentSum currentSum - removed nums[i]; } // 此时左边选了最小的 n 个和为 currentSum右边选最大的 n 个和为 sufMax[i1] // 注意上面的循环中 sufMax 的下标对应的是起始位置。 // 当我们在处理 nums[i] 并将其加入左边集合后左边的有效范围是 [0, i]共 i1 个元素从中选 n 个。 // 此时分割点实际上变成了 i1。右边的范围是 [i1, m-1]。 // 所以我们要用 sufMax[i1]。 long diff currentSum - sufMax[i 1]; if (diff ans) { ans diff; } } return ans; }}关键点解析堆的选择求前缀最小 n 个数之和用最大堆。堆顶是这 n 个数里最大的如果遇到更小的数就把堆顶踢掉这样总和才会变小。求后缀最大 n 个数之和用最小堆。堆顶是这 n 个数里最小的如果遇到更大的数就把堆顶踢掉这样总和才会变大。边界处理数组长度为 3n。分割点 i 的含义左边部分从 0 到 i-1 中选右边部分从 i 到 3n-1 中选。i 的最小值是 n左边至少 n 个最大值是 2n右边至少 n 个。代码中 sufMax 数组的下标对应右边部分的起始索引。数据类型题目要求返回 long因为元素和可能超出 int 范围中间计算过程务必使用 long。这个算法能够高效地在 O(N log N) 时间内解决问题适用于 N 较大的情况。