class Solution {
public:
long long minimumDifference(vector<int>& nums) {
}
};
2163. 删除元素后和的最小差值
给你一个下标从 0 开始的整数数组 nums ，它包含 3 * n 个元素。
你可以从 nums 中删除 恰好 n 个元素，剩下的 2 * n 个元素将会被分成两个 相同大小 的部分。
n 个元素属于第一部分，它们的和记为 sumfirst 。n 个元素属于第二部分，它们的和记为 sumsecond 。两部分和的 差值 记为 sumfirst - sumsecond 。
sumfirst = 3 且 sumsecond = 2 ，它们的差值为 1 。sumfirst = 2 且 sumsecond = 3 ，它们的差值为 -1 。请你返回删除 n 个元素之后，剩下两部分和的 差值的最小值 是多少。
示例 1：
输入：nums = [3,1,2] 输出：-1 解释：nums 有 3 个元素，所以 n = 1 。 所以我们需要从 nums 中删除 1 个元素，并将剩下的元素分成两部分。 - 如果我们删除 nums[0] = 3 ，数组变为 [1,2] 。两部分和的差值为 1 - 2 = -1 。 - 如果我们删除 nums[1] = 1 ，数组变为 [3,2] 。两部分和的差值为 3 - 2 = 1 。 - 如果我们删除 nums[2] = 2 ，数组变为 [3,1] 。两部分和的差值为 3 - 1 = 2 。 两部分和的最小差值为 min(-1,1,2) = -1 。
示例 2：
输入：nums = [7,9,5,8,1,3] 输出：1 解释：n = 2 。所以我们需要删除 2 个元素，并将剩下元素分为 2 部分。 如果我们删除元素 nums[2] = 5 和 nums[3] = 8 ，剩下元素为 [7,9,1,3] 。和的差值为 (7+9) - (1+3) = 12 。 为了得到最小差值，我们应该删除 nums[1] = 9 和 nums[4] = 1 ，剩下的元素为 [7,5,8,3] 。和的差值为 (7+5) - (8+3) = 1 。 观察可知，最优答案为 1 。
提示：
nums.length == 3 * n1 <= n <= 1051 <= nums[i] <= 105原站题解
java 解法, 执行用时: 210 ms, 内存消耗: 86.5 MB, 提交时间: 2023-09-26 20:16:58
class Solution {
public long minimumDifference(int[] nums) {
var m = nums.length;
var n = m / 3;
var minPQ = new PriorityQueue<Integer>();
var sum = 0L;
for (var i = m - n; i < m; i++) {
minPQ.add(nums[i]);
sum += nums[i];
}
var sufMax = new long[m - n + 1]; // 后缀最大和
sufMax[m - n] = sum;
for (var i = m - n - 1; i >= n; --i) {
minPQ.add(nums[i]);
sum += nums[i] - minPQ.poll();
sufMax[i] = sum;
}
var maxPQ = new PriorityQueue<Integer>(Collections.reverseOrder());
var preMin = 0L; // 前缀最小和
for (var i = 0; i < n; ++i) {
maxPQ.add(nums[i]);
preMin += nums[i];
}
var ans = preMin - sufMax[n];
for (var i = n; i < m - n; ++i) {
maxPQ.add(nums[i]);
preMin += nums[i] - maxPQ.poll();
ans = Math.min(ans, preMin - sufMax[i + 1]);
}
return ans;
}
}
cpp 解法, 执行用时: 400 ms, 内存消耗: 133.3 MB, 提交时间: 2023-09-26 20:16:45
class Solution {
public:
long long minimumDifference(vector<int> &nums) {
int m = nums.size(), n = m / 3;
priority_queue<int, vector<int>, greater<int>> minPQ;
long sum = 0L;
for (int i = m - n; i < m; ++i) {
minPQ.push(nums[i]);
sum += nums[i];
}
vector<long> sufMax(m - n + 1); // 后缀最大和
sufMax[m - n] = sum;
for (int i = m - n - 1; i >= n; --i) {
minPQ.push(nums[i]);
sum += nums[i] - minPQ.top();
minPQ.pop();
sufMax[i] = sum;
}
priority_queue<int> maxPQ;
long preMin = 0L; // 前缀最小和
for (int i = 0; i < n; ++i) {
maxPQ.push(nums[i]);
preMin += nums[i];
}
long ans = preMin - sufMax[n];
for (int i = n; i < m - n; ++i) {
maxPQ.push(nums[i]);
preMin += nums[i] - maxPQ.top();
maxPQ.pop();
ans = min(ans, preMin - sufMax[i + 1]);
}
return ans;
}
};
golang 解法, 执行用时: 260 ms, 内存消耗: 14 MB, 提交时间: 2023-09-26 20:15:55
func minimumDifference(nums []int) int64 {
m := len(nums)
n := m / 3
minPQ := minHeap{nums[m-n:]}
heap.Init(&minPQ)
sum := 0
for _, v := range nums[m-n:] {
sum += v
}
sufMax := make([]int, m-n+1) // 后缀最大和
sufMax[m-n] = sum
for i := m - n - 1; i >= n; i-- {
if v := nums[i]; v > minPQ.IntSlice[0] {
sum += v - minPQ.IntSlice[0]
minPQ.IntSlice[0] = v
heap.Fix(&minPQ, 0)
}
sufMax[i] = sum
}
maxPQ := maxHeap{nums[:n]}
heap.Init(&maxPQ)
preMin := 0 // 前缀最小和
for _, v := range nums[:n] {
preMin += v
}
ans := preMin - sufMax[n]
for i := n; i < m-n; i++ {
if v := nums[i]; v < maxPQ.IntSlice[0] {
preMin += v - maxPQ.IntSlice[0]
maxPQ.IntSlice[0] = v
heap.Fix(&maxPQ, 0)
}
ans = min(ans, preMin-sufMax[i+1])
}
return int64(ans)
}
type minHeap struct{ sort.IntSlice }
func (minHeap) Push(interface{}) {}
func (minHeap) Pop() (_ interface{}) { return }
type maxHeap struct{ sort.IntSlice }
func (h maxHeap) Less(i, j int) bool { return h.IntSlice[i] > h.IntSlice[j] }
func (maxHeap) Push(interface{}) {}
func (maxHeap) Pop() (_ interface{}) { return }
func min(a, b int) int { if a > b { return b }; return a }
python3 解法, 执行用时: 396 ms, 内存消耗: 45 MB, 提交时间: 2023-09-26 20:15:43
class Solution:
def minimumDifference(self, nums: List[int]) -> int:
m = len(nums)
n = m // 3
min_pq = nums[-n:]
heapify(min_pq)
suf_max = [0] * (m - n + 1) # 后缀最大和
suf_max[-1] = s = sum(min_pq)
for i in range(m - n - 1, n - 1, -1):
s += nums[i] - heappushpop(min_pq, nums[i])
suf_max[i] = s
max_pq = [-v for v in nums[:n]] # 所有元素取反当最大堆
heapify(max_pq)
pre_min = -sum(max_pq) # 前缀最小和
ans = pre_min - suf_max[n]
for i in range(n, m - n):
pre_min += nums[i] + heappushpop(max_pq, -nums[i])
ans = min(ans, pre_min - suf_max[i + 1])
return ans