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\ast 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 个元素可供选择。

通过这“三步走”战略，我们把一个复杂的、看似需要回溯搜索的问题，转化成了一个结构清晰、逻辑流畅的动态规划+数据结构优化问题。