Hard

题目描述

给你一个下标从 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 * n
  • 1 <= n <= 10^5
  • 1 <= nums[i] <= 10^5

解题思路

解题思路

要让差值 sumfirst - sumsecond 最小，我们需要让第一部分的和尽可能小，第二部分的和尽可能大。

关键观察：我们可以枚举分割点，对于每个可能的分割位置，计算左边能取到的最小n个数的和，以及右边能取到的最大n个数的和。

核心思路：

  1. 预处理出数组每个位置左边（包括该位置）至少n个元素中最小n个数的和
  2. 预处理出数组每个位置右边（包括该位置）至少n个元素中最大n个数的和
  3. 枚举所有可能的分割点，计算差值的最小值

具体实现：

  • 使用最大堆维护左边最小的n个数
  • 使用最小堆维护右边最大的n个数
  • 从左到右扫描计算 leftMin[i]：位置i左边（含i）最小n个数的和
  • 从右到左扫描计算 rightMax[i]：位置i右边（含i）最大n个数的和

分割点i必须满足：左边至少有n个元素，右边至少有n个元素，即 n-1 <= i <= 2*n-1。

时间复杂度： O(n log n)
空间复杂度： O(n)

代码实现

class Solution {
public:
    long long minimumDifference(vector<int>& nums) {
        int n = nums.size() / 3;
        
        // 计算每个位置左边最小n个数的和
        vector<long long> leftMin(3 * n);
        priority_queue<int> maxHeap; // 维护最小的n个数
        long long sum = 0;
        
        for (int i = 0; i < 3 * n; i++) {
            maxHeap.push(nums[i]);
            sum += nums[i];
            
            if (maxHeap.size() > n) {
                sum -= maxHeap.top();
                maxHeap.pop();
            }
            
            if (maxHeap.size() == n) {
                leftMin[i] = sum;
            }
        }
        
        // 计算每个位置右边最大n个数的和
        vector<long long> rightMax(3 * n);
        priority_queue<int, vector<int>, greater<int>> minHeap; // 维护最大的n个数
        sum = 0;
        
        for (int i = 3 * n - 1; i >= 0; i--) {
            minHeap.push(nums[i]);
            sum += nums[i];
            
            if (minHeap.size() > n) {
                sum -= minHeap.top();
                minHeap.pop();
            }
            
            if (minHeap.size() == n) {
                rightMax[i] = sum;
            }
        }
        
        // 找最小差值
        long long result = LLONG_MAX;
        for (int i = n - 1; i < 2 * n; i++) {
            result = min(result, leftMin[i] - rightMax[i + 1]);
        }
        
        return result;
    }
};

class Solution:
    def minimumDifference(self, nums: List[int]) -> int:
        import heapq
        
        n = len(nums) // 3
        
        # 计算每个位置左边最小n个数的和
        left_min = [0] * (3 * n)
        max_heap = []  # 维护最小的n个数（用负数模拟最大堆）
        total = 0
        
        for i in range(3 * n):
            heapq.heappush(max_heap, -nums[i])
            total += nums[i]
            
            if len(max_heap) > n:
                total += heapq.heappop(max_heap)  # 注意这里是加法，因为存的是负数
            
            if len(max_heap) == n:
                left_min[i] = total
        
        # 计算每个位置右边最大n个数的和
        right_max = [0] * (3 * n)
        min_heap = []  # 维护最大的n个数
        total = 0
        
        for i in range(3 * n - 1, -1, -1):
            heapq.heappush(min_heap, nums[i])
            total += nums[i]
            
            if len(min_heap) > n:
                total -= heapq.heappop(min_heap)
            
            if len(min_heap) == n:
                right_max[i] = total
        
        # 找最小差值
        result = float('inf')
        for i in range(n - 1, 2 * n):
            result = min(result, left_min[i] - right_max[i + 1])
        
        return result

public class Solution {
    public long MinimumDifference(int[] nums) {
        int n = nums.Length / 3;
        
        // 计算每个位置左边最小n个数的和
        long[] leftMin = new long[3 * n];
        var maxHeap = new PriorityQueue<int, int>(Comparer<int>.Create((a, b) => b.CompareTo(a)));
        long sum = 0;
        
        for (int i = 0; i < 3 * n; i++) {
            maxHeap.Enqueue(nums[i], nums[i]);
            sum += nums[i];
            
            if (maxHeap.Count > n) {
                sum -= maxHeap.Dequeue();
            }
            
            if (maxHeap.Count == n) {
                leftMin[i] = sum;
            }
        }
        
        // 计算每个位置右边最大n个数的和
        long[] rightMax = new long[3 * n];
        var minHeap = new PriorityQueue<int, int>();
        sum = 0;
        
        for (int i = 3 * n - 1; i >= 0; i--) {
            minHeap.Enqueue(nums[i], nums[i]);
            sum += nums[i];
            
            if (minHeap.Count > n) {
                sum -= minHeap.Dequeue();
            }
            
            if (minHeap.Count == n) {
                rightMax[i] = sum;
            }
        }
        
        // 找最小差值
        long result = long.MaxValue;
        for (int i = n - 1; i < 2 * n; i++) {
            result = Math.Min(result, leftMin[i] - rightMax[i + 1]);
        }
        
        return result;
    }
}

var minimumDifference = function(nums) {
    const n = nums.length / 3;
    
    // minLeft[i] = minimum sum of n elements from nums[0...i]
    const minLeft = new Array(nums.length);
    let minHeap = [];
    let sum = 0;
    
    // Build min heap for first n elements
    for (let i = 0; i < n; i++) {
        minHeap.push(nums[i]);
        sum += nums[i];
    }
    minHeap.sort((a, b) => b - a); // max heap for getting minimum sum
    minLeft[n - 1] = sum;
    
    // Fill minLeft array
    for (let i = n; i < 2 * n; i++) {
        if (nums[i] < minHeap[0]) {
            sum -= minHeap[0];
            minHeap[0] = nums[i];
            sum += nums[i];
            minHeap.sort((a, b) => b - a);
        }
        minLeft[i] = sum;
    }
    
    // maxRight[i] = maximum sum of n elements from nums[i...2n-1]
    const maxRight = new Array(nums.length);
    let maxHeap = [];
    sum = 0;
    
    // Build max heap for last n elements
    for (let i = 2 * n; i < 3 * n; i++) {
        maxHeap.push(nums[i]);
        sum += nums[i];
    }
    maxHeap.sort((a, b) => a - b); // min heap for getting maximum sum
    maxRight[2 * n] = sum;
    
    // Fill maxRight array
    for (let i = 2 * n - 1; i >= n; i--) {
        if (nums[i] > maxHeap[0]) {
            sum -= maxHeap[0];
            maxHeap[0] = nums[i];
            sum += nums[i];
            maxHeap.sort((a, b) => a - b);
        }
        maxRight[i] = sum;
    }
    
    let result = Infinity;
    for (let i = n - 1; i < 2 * n; i++) {
        result = Math.min(result, minLeft[i] - maxRight[i + 1]);
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度大小
时间复杂度O(n log n)
空间复杂度O(n)
  • 时间复杂度：需要遍历3n个元素，每次堆操作的时间复杂度为O(log n)
  • 空间复杂度：使用了两个大小为n的堆，以及两个大小为3n的数组来存储预处理结果

相关题目