目标
给你一个下标从 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 <= 10^5
- 0 <= nums[i] <= 10^9
- 0 <= p <= (nums.length)/2
思路
取 p 个不包含相同下标的下标对，使这 p 个下标对的绝对差的最大值最小。
最小化最大值，优先考虑二分查找。问题是如何判断绝对差小于当前值的数对个数。
参考 2560.打家劫舍IV，可以使用动态规划或者贪心。
关键是贪心策略，只要相邻元素的绝对差小于二分的最大绝对差就是可选的。
代码
/**
* @date 2025-06-13 0:09
*/
public class MinimizeMax2616 {
public int minimizeMax(int[] nums, int p) {
Arrays.sort(nums);
int r = nums[nums.length - 1] - nums[0];
int l = 0;
int mid = l + (r - l) / 2;
while (l <= r) {
if (check(nums, p, mid)) {
r = mid - 1;
} else {
l = mid + 1;
}
mid = l + (r - l) / 2;
}
return l;
}
public boolean check(int[] nums, int p, int cur) {
int n = nums.length;
for (int i = 1; i < n && p > 0; i++) {
if (nums[i] - nums[i - 1] <= cur) {
i++;
p--;
}
}
return p == 0;
}
}
性能
