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

题目：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)/2
        if solve(mid,nums,p)==true {
            right=mid
        }else{
            left=mid+1
        }
    }
    return left
}
func solve(u int,nums []int, p int) bool {
    ans:=0
    for i:=0;i+1<len(nums);i++ {
        if nums[i+1]-nums[i]<=u {
            i++
            ans++
        }
    }
    return ans>=p
}