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

题目链接：2517. 礼盒的最大甜蜜度（中等）

算法原理：

解法：二分查找+贪心

跟上题极其相似👇

D.二分查找－二分答案－最大化最小值——3281. 范围内整数的最大得分

49ms击败67.69%

时间复杂度O(Nlogn)

任意两种糖果价格绝对差的最小值=排序后，任意两种相邻糖果价格绝对差的最小值

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

①目标变量：甜蜜度（最小绝对差）

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

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

具体步骤：

①确定边界：

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

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

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

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

答疑

Q1：此题不同于上一题区间D.二分查找－二分答案－最大化最小值——3281. 范围内整数的最大得分，上一题的点只需落到区间中就行，但这题我们要找的各个点是个确定的值啊，比如说当最小差为9时，肯定比8大啊，按照最右端点的写法，9符合条件，应该去尝试10，但我们不应该去尝试8吗？

确实应该去尝试10，因为最小差为9时符合条件，那么8也一定符合条件，但8<9，而我们要找的就是最大化最小值，9是最小值，我们要最大化，最大化就应该去找大于9的数，所以找10是对的

Java代码：

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