删除元素后和的最小差值

标签: 数组 动态规划 堆（优先队列）

难度: 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 <= 105
  • 1 <= nums[i] <= 105

Submission

运行时间: 276 ms

内存: 48.6 MB

class Solution:
    def minimumDifference(self, nums: List[int]) -> int:
        N=len(nums)
        n =N//3
        left = [0]*n
        right = [0]*n
        neg = [-x for x in nums]
        def f(a,b):
            q = a[:n]
            heapq.heapify(q)
            s = sum(a[:n])
            b[-1] = s
            for x in a[n:2*n]:
                if q[0] < x:
                    s += x - heapq.heappushpop(q, x)
                b.append(s)
        f(neg, left)
        f(nums[::-1],right)
        return min( -right[i]-left[3*n - 2- i] for i in range(n-1, 2*n))

Explain

为了求差值最小的两部分和，我们可以利用两个最小堆来维护每一种可能的前n和后n元素的和。这个解决方案首先定义一个辅助函数f，该函数使用最小堆来计算前n个元素的最大可能和。对于数组的前半部分，我们使用一个负数数组来将最小堆转换成最大堆，从而可以获得前n个元素的最大和。对于数组的后半部分，我们直接使用一个最小堆来维护后n个元素的最小和。这样，对于每个元素，我们可以快速更新堆和当前的和，如果新元素比堆顶要大。最后，通过比较所有可能的前后n元素和的组合，找到最小的差值。

时间复杂度: O(n log n)

空间复杂度: O(n)

class Solution:
    def minimumDifference(self, nums: List[int]) -> int:
        N = len(nums)
        n = N // 3
        left = [0] * n
        right = [0] * n
        neg = [-x for x in nums]
        def f(a, b):
            q = a[:n]
            heapq.heapify(q)
            s = sum(a[:n])
            b[-1] = s
            for x in a[n:2*n]:
                if q[0] < x:
                    s += x - heapq.heappushpop(q, x)
                b.append(s)
        f(neg, left)  # Process the first n elements for maximum sums
        f(nums[::-1], right)  # Process the last n elements for minimum sums
        return min(-right[i] - left[3 * n - 2 - i] for i in range(n - 1, 2 * n))  # Compute minimal difference

Explore

在计算前n个元素的最大和时，我们需要找到前n个元素中最大的元素和。由于最小堆默认是提取出最小的元素，因此通过将所有元素取负数后，原本较大的元素会变成较小的负数，这样就可以利用最小堆的性质来维护这些原始元素的最大值。在堆中，最小的负数对应着原数组中的最大数。这样操作可以有效地使用标准库中的最小堆来实现最大堆的功能。

在函数f中，如果新元素比堆顶元素大，进行替换的主要目的是更新当前的和以维持堆中的n个元素为当前遍历到的元素中的最大或最小n个。这样的替换确保了我们总是保持当前遍历的元素中的最大或最小累积和。替换操作后，堆重新调整，保持堆的性质，这使得我们能够快速计算出当前最优的和，并随着更多元素的遍历进行实时更新。

在计算后n个元素的最小和时，选择对nums数组进行反转是为了方便使用相同的处理逻辑来计算最小和。通过反转数组，原本数组的末尾n个元素变成了反转后数组的前n个元素，这样就可以复用前面定义的函数f，来计算这些元素的最小和。反转后，数组的遍历方式与处理前n个元素的方法相同，从而简化了代码的复杂性并保持了一致的处理逻辑。

在f函数中，b数组用于记录每一步中的累积和。这是通过初始化一个堆和累积和变量，然后遍历元素来维护这个累积和实现的。在遍历过程中，每次堆的内容更新（如有新元素替换堆顶元素），累积和也相应地更新。这个累积和随后被记录在b数组中。具体地，b数组的每个位置记录了从数组开始到当前元素的最优和状态。通过这种方式，b数组能够准确地反映出在每个阶段堆中元素可能达到的最大或最小和。