2616-最小化数对的最大差值

Raphael Liu Lv10
  2023-09-13 00:47:26 2023-09-13 00:47:26 Created   2023-09-13 16:06:25 2023-09-13 16:06:25 Updated    

给你一个下标从 0 开始的整数数组 nums 和一个整数 p 。请你从 nums 中找到 p
个下标对，每个下标对对应数值取差值，你需要使得这 p 个差值的 最大值 最小 。同时，你需要确保每个下标在这 p
个下标对中最多出现一次。

对于一个下标对 i 和 j ，这一对的差值为 |nums[i] - nums[j]| ，其中 |x| 表示 x 的 绝对值 。

请你返回 p 个下标对对应数值 最大差值 的 最小值 。

示例 1：

**输入：** nums = [10,1,2,7,1,3], p = 2
**输出：** 1
**解释：** 第一个下标对选择 1 和 4 ，第二个下标对选择 2 和 5 。
最大差值为 max(|nums[1] - nums[4]|, |nums[2] - nums[5]|) = max(0, 1) = 1 。所以我们返回 1 。

示例 2：

**输入：** nums = [4,2,1,2], p = 1
**输出：** 0
**解释：** 选择下标 1 和 3 构成下标对。差值为 |2 - 2| = 0 ，这是最大差值的最小值。

提示：

  • 1 <= nums.length <= 105
  • 0 <= nums[i] <= 109
  • 0 <= p <= (nums.length)/2

本题视频讲解

见【周赛 340】 。

前置知识：二分

见 二分查找【基础算法精讲 04】 。

提示 1

看到「最大化最小值」或者「最小化最大值」就要想到二分答案，这是一个固定的套路。

为什么？一般来说，二分的值越大，越能/不能满足要求；二分的值越小，越不能/能满足要求，有单调性，可以二分。

更多题目见文末的题单。

提示 2

二分数对中的最大差值 mx。

由于下标和答案无关，可以先排序。为了让匹配的数对尽量多，应尽量选相邻的元素，这样更能满足要求。例如 [1,2,3,4]，如果 1,3 匹配，2,4 匹配，最大差值是 2；而如果 1,2 相邻匹配，3,4 相邻匹配，最大差值只有 1。

我们来算一算最多能匹配多少个数对：

  • 如果可以选 nums}[0] 和 nums}[1]，那么答案等于「n-2 个数的最多数对个数」+1。
  • 如果不选 nums}[0]，那么答案等于「n-1 个数的最多数对个数」。
  • 这两种情况取最大值。

这看上去很像 198. 打家劫舍 ，可以用动态规划实现。

也可以用贪心做：

  • 注意到，「n-1 个数的最多数对个数」不会超过「n-3 个数的最多数对个数」+1。这里 +1 表示选 nums}[1] 和 nums}[2]。
  • 由于「n-2 个数的最多数对个数」\ge「n-3 个数的最多数对个数」，所以如果可以选 nums}[0] 和 nums}[1]，那么直接选就行。
  • 依此类推，不断缩小问题规模。所以遍历一遍数组就能求出最多数对个数，具体见代码。
[sol1-Python3]
1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
    def minimizeMax(self, nums: List[int], p: int) -> int:
        nums.sort()
        def f(mx: int) -> int:
            cnt = i = 0
            while i < len(nums) - 1:
                if nums[i + 1] - nums[i] <= mx:  # 都选
                    cnt += 1
                    i += 2
                else:  # 不选 nums[i]
                    i += 1
            return cnt
        return bisect_left(range(nums[-1] - nums[0]), p, key=f)
[sol1-Java]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public int minimizeMax(int[] nums, int p) {
        Arrays.sort(nums);
        int n = nums.length, left = -1, right = nums[n - 1] - nums[0]; // 开区间
        while (left + 1 < right) { // 开区间
            int mid = (left + right) >>> 1, cnt = 0;
            for (int i = 0; i < n - 1; ++i)
                if (nums[i + 1] - nums[i] <= mid) { // 都选
                    ++cnt;
                    ++i;
                }
            if (cnt >= p) right = mid;
            else left = mid;
        }
        return right;
    }
}
[sol1-C++]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    int minimizeMax(vector<int> &nums, int p) {
        sort(nums.begin(), nums.end());
        int left = -1, right = nums.back() - nums[0]; // 开区间
        while (left + 1 < right) { // 开区间
            int mid = left + (right - left) / 2, cnt = 0;
            for (int i = 0; i < nums.size() - 1; ++i)
                if (nums[i + 1] - nums[i] <= mid) { // 都选
                    ++cnt;
                    ++i;
                }
            (cnt >= p ? right : left) = mid;
        }
        return right;
    }
};
[sol1-Go]
1
2
3
4
5
6
7
8
9
10
11
12
13
func minimizeMax(nums []int, p int) int {
	sort.Ints(nums)
	return sort.Search(1e9, func(mx int) bool {
		cnt := 0
		for i := 0; i < len(nums)-1; i++ {
			if nums[i+1]-nums[i] <= mx { // 都选
				cnt++
				i++
			}
		}
		return cnt >= p
	})
}

复杂度分析

  • 时间复杂度：O(n\log n + n\log U)，其中 n 为 nums 的长度，U=\max(\textit{nums})-\min(\textit{nums})。
  • 空间复杂度：O(1)。忽略排序时的栈空间，仅用到若干额外变量。

二分答案·题单

二分答案

最小化最大值

最大化最小值

 Comments
On this page
2616-最小化数对的最大差值
  1. 本题视频讲解
  2. 前置知识：二分
  3. 提示 1
  4. 提示 2
  5. 复杂度分析
  6. 二分答案·题单