D.二分查找－二分答案－最大化最小值——1552. 两球之间的磁力

题目链接：1552. 两球之间的磁力（中等）

算法原理：

解法：二分查找+贪心

跟上题不能说极其相似，只能说一摸一样😂改个变量名直接AC了👇

D.二分查找－二分答案－最大化最小值——2517. 礼盒的最大甜蜜度

49ms击败81.33%

时间复杂度O(Nlogn)

任意两球磁力绝对差的最小值=排序后，任意两相邻i小球磁力绝对差的最小值

因为排序后不相邻的数作差一定≥相邻数作的差，min时肯定不会被取到

①目标变量：磁力（最小绝对差）

②目标条件：在当前磁力情况下，所选k个数中任意两数差值≥当前磁力，且当前磁力要最大化

③转换逻辑：当前磁力为mid时，能否选出k个数，使得任意两个选中的数差值≥mid

具体步骤：

①确定边界：

left：0，所有数选同一个值，最小差为0

right：position[n-1]-position[0]，排序后，最大差=最大值-最小值

②确定二分模型：磁力 ↑ 能选择的数的数量 ↓ 呈负相关单调，由于要最大化磁力，因此采用最右端点模型

③check方法设计：采用双指针贪心的方法，贪心的点在于第一个点直接选position[0]，以便给后续值留下更大差值空间，在此之后再用双指针的方法：prev记录前一个符合条件的值，只要当前position-prev≥mid，说明就找到了一个符合条件的点，计数cnt++，当计数≥k时就可以返回了

Java代码：

class Solution { public int maxDistance(int[] position, int m) { Arrays.sort(position); int n=position.length; int left=0,right=position[n-1]-position[0]; while(left<right){ int mid=left+(right-left+1)/2; if(!check(mid,position,m)) right=mid-1; else left=mid; } return left; } //判断能否选出k个数，使得任意两个选中的数差值≥mid private boolean check(int mid,int[] position,int m){ int cnt=1; int prev=position[0]; for(int i=1;i<position.length;i++){ if(position[i]-prev>=mid){ cnt++; prev=position[i]; //提前满足，提前返回 if(cnt>=m) return true; } } return cnt>=m; } }