最小化数对的最大差值
给你一个下标从 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
来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/minimize-the-maximum-difference-of-pairs
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
解题思路
二分答案+贪心。其中存在很多思考上的细节，自己对二分答案和区间也不是特别熟悉并不能解释得十分明白，加上最近时间还是有点紧张，先mark一下。
code
class Solution {
public:
// 最小化最大值 -> 二分答案
// 二分查找 -> 在一个具有二段性的数据上进行查找
// 二分答案 -> 答案在一个区间内，在答案区间中二分直到找到最优的答案
// 答案属于一个区间，区间对题目的某一个量具有单调性
// 最小化最大值：二分最大值时在满足条件时尽量让答案更小也就是r = mid
// 最大化最小值：二分最小值时在满足条件时尽量让答案更大也就是l = mid
//例子：本题就是最小化最大值
//答案区间就是自然数0 1 2 …… 9 ……
//假如二分的中点是9 判断是否存在p个数对使得最大值为9
//如果存在，显然应该往左侧区间二分否则往右侧区间二分
//最小化最大值：答案ans, < ans 和>= ans 我们希望找到大于等于ans的左侧区间并且左侧区间都是可以满足p个数对的
//恰好选p对数比较难写，选大于等于p对
//贪心：如果前面两个可选，那么必选
bool check(int mid,vector<int> & nums,int & p)
{
int cnt = 0,i = 0;
while(i < nums.size() -1)
{
//满足就都选上
if(nums[i+1] - nums[i] <= mid)
{
cnt ++;
i += 2;
}
//不满足跳过
else i ++;
}
return cnt >= p;
}
int minimizeMax(vector<int>& nums, int p) {
sort(nums.begin(),nums.end());
int n = nums.size();
int l = 0,r = nums[n-1] - nums[0];
while(l < r)
{
int mid = (l + r) / 2;
if(check(mid,nums,p)) r = mid;
else l = mid + 1;
}
return r;
}
};