What is the core pattern for solving the Minimum Difference in Sums After Removal of Elements problem?

The core pattern is state transition dynamic programming combined with heap operations to manage and optimize subarray sum calculations.

How can heaps be useful in solving the problem?

Heaps allow us to efficiently manage the largest and smallest elements of the remaining array, helping in minimizing the sum difference.

Why is dynamic programming essential for this problem?

Dynamic programming helps by efficiently tracking and calculating the sums after removing subsequences, reducing the problem's complexity.

What time complexity can I expect when solving the problem?

The expected time complexity is O(n log n), primarily due to heap operations during the state transitions.

How can I handle edge cases in the Minimum Difference in Sums After Removal of Elements problem?

Ensure correct handling of small and large values of n, and be mindful of the heap and partitioning operations during dynamic programming transitions.

#2163

Hard

auto_awesome状态·转移·动态规划

LeetCode 题解工作台

删除元素后和的最小差值

给你一个下标从 0 开始的整数数组 nums ，它包含 3 * n 个元素。你可以从 nums 中删除恰好 n 个元素，剩下的 2 * n 个元素将会被分成两个相同大小的部分。前面 n 个元素属于第一部分，它们的和记为 sum first 。后面 n 个元素属于第二部分，它们的和记为 s…

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

题目描述

给你一个下标从 0 开始的整数数组 nums ，它包含 3 * n 个元素。

你可以从 nums 中删除恰好 n 个元素，剩下的 2 * n 个元素将会被分成两个 相同大小 的部分。

前面 n 个元素属于第一部分，它们的和记为 sum_first 。
后面 n 个元素属于第二部分，它们的和记为 sum_second 。

两部分和的差值记为 sum_first - sum_second 。

比方说，sum_first = 3 且 sum_second = 2 ，它们的差值为 1 。
再比方，sum_first = 2 且 sum_second = 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⁵
1 <= nums[i] <= 10⁵

lightbulb

解题思路

方法一：优先队列（大小根堆）+ 前后缀和 + 枚举分割点

题目实际上等价于在 $nums$ 中找到一个分割点，将数组分成左右两部分，在前一部分中选取最小的 $n$ 个元素，在后一部分中选取最大的 $n$ 个元素，使得两部分和的差值最小。

我们可以用一个大根堆维护前缀中最小的 $n$ 个元素，用一个小根堆维护后缀中最大的 $n$ 个元素。我们定义 $pre[i]$ 表示在数组 $nums$ 的前 $i$ 个元素中选择最小的 $n$ 个元素的和，定义 $suf[i]$ 表示从数组第 $i$ 个元素到最后一个元素中选择最大的 $n$ 个元素的和。在维护大小根堆的过程中，更新 $pre[i]$ 和 $suf[i]$ 的值。

最后，我们在 $i \in [n, 2n]$ 的范围内枚举分割点，计算 $pre[i] - suf[i + 1]$ 的值，取最小值即可。

时间复杂度 $O(n \times \log n)$ ，空间复杂度 $O(n)$ 。其中 $n$ 为数组 $nums$ 的长度。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

class Solution:
    def minimumDifference(self, nums: List[int]) -> int:
        m = len(nums)
        n = m // 3

        s = 0
        pre = [0] * (m + 1)
        q1 = []
        for i, x in enumerate(nums[: n * 2], 1):
            s += x
            heappush(q1, -x)
            if len(q1) > n:
                s -= -heappop(q1)
            pre[i] = s

        s = 0
        suf = [0] * (m + 1)
        q2 = []
        for i in range(m, n, -1):
            x = nums[i - 1]
            s += x
            heappush(q2, x)
            if len(q2) > n:
                s -= heappop(q2)
            suf[i] = s

        return min(pre[i] - suf[i + 1] for i in range(n, n * 2 + 1))

speed

复杂度分析

指标	值
时间	O(n \log n)
空间	O(n)

psychology

面试官常问的追问

外企场景

question_mark
Tests the candidate's ability to apply dynamic programming with state transitions.
question_mark
Evaluates the candidate's knowledge of heap operations for optimizing subarray sum calculations.
question_mark
Checks the ability to optimize performance for large input sizes (up to 3 * 10^5 elements).

warning

常见陷阱

外企场景

error
Forgetting to handle the edge case where n is very small or large.
error
Inefficient heap usage which could cause time complexity to exceed the limit.
error
Incorrect partitioning of the remaining elements after removing the subsequence.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Variation with a constraint on the value of n for additional optimization challenges.
arrow_right_alt
Problem with multiple possible subsequences to remove, requiring additional considerations for efficiency.
arrow_right_alt
Variant that requires splitting the array into more than two parts instead of two.

help

常见问题

外企场景

继续练习

#2054 两个最好的不重叠活动 #2617 网格图中最少访问的格子数 #1696 跳跃游戏 VI