(nice!!!)(LeetCode 每日一题) 2616. 最小化数对的最大差值 (二分查找)

思路：二分查找，时间复杂度0(n log( 10^9 ) )。

对差值进行二分，最大差值为max(nums[i])-min(nums[i])，最小差值为0。细节看注释

C++版本：

class Solution {
public:bool solve(int u,vector<int>& nums,int p){// 差值小于u的数量int ans=0;for(int i=0;i+1<nums.size();i++){if(nums[i+1]-nums[i]<=u){ans++;i++;}}return ans>=p;}int minimizeMax(vector<int>& nums, int p) {// 先升序排序sort(nums.begin(),nums.end());int n=nums.size();// 最小差值、最大差值int left=0,right=nums[n-1]-nums[0];// 二分查找while(left<right){int mid=(left+right)/2;// 符合，差值可缩小if(solve(mid,nums,p)) right=mid;else left=mid+1;}return left;}
};

JAVA版本：

class Solution {boolean solve(int u,int[] nums, int p){int ans=0;for(int i=0;i+1<nums.length;i++){if(nums[i+1]-nums[i]<=u){ans++;i++;}}return ans>=p;}public int minimizeMax(int[] nums, int p) {Arrays.sort(nums);int n=nums.length;int left=0,right=nums[n-1]-nums[0];while(left<right){int mid=(left+right)/2;if(solve(mid,nums,p)) right=mid;else left=mid+1;}return left;}
}

Go版本：

func minimizeMax(nums []int, p int) int {n:=len(nums)slices.Sort(nums)left,right:=0,nums[n-1]-nums[0]for left<right {mid:=(left+right)/2if solve(mid,nums,p)==true {right=mid}else{left=mid+1}}return left
}
func solve(u int,nums []int, p int) bool {ans:=0for i:=0;i+1<len(nums);i++ {if nums[i+1]-nums[i]<=u {i++ans++}}return ans>=p
}