【每日一题Day224】LC2517礼盒的最大甜蜜度

这篇具有很好参考价值的文章主要介绍了【每日一题Day224】LC2517礼盒的最大甜蜜度 | 二分答案。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

礼盒的最大甜蜜度【LC2517】

You are given an array of positive integers price where price[i] denotes the price of the ith candy and a positive integer k.

The store sells baskets of k distinct candies. The tastiness of a candy basket is the smallest absolute difference of the prices of any two candies in the basket.

Return the maximum tastiness of a candy basket.

最大化最小化类似题目

思路：使用二分查找的方式寻找最大甜蜜度
- 本题的单调性为：当**最小甜蜜度【数组中任意两个元素的差值的绝对值的最小值】**越大，糖果的可以选择的种类越小【选取的数组中的元素个数】，因此可以通过二分查找法找到最终答案
- 将题意转化为：当选取的数量一定时，寻找最小甜蜜度的最大值 $y$ ，二分查找的下限为0，上限为数组中最大元素与最小元素的差值/（k-1）
实现
- 首先对price数组进行升序排序
- 然后进行二分查找，当二分查找最小甜蜜度 $y$ 时，需要判断能否取出 $k$ 种糖果，如果能取出 $k$ 种糖果，那么我们可以增大差值，已获得更大的最小甜蜜度；如果不能取出 $k$ 中糖果，那么减小差值
- 每次查找成功，记录当前的最小甜蜜度，最后一次的最小甜蜜度即为最大最小甜蜜度
- 如何判断当前的差值能够取出多少种糖果？
  
  模拟迭代，第一种糖果取 $p r i ce [0]$ ，第一种糖果取 $p r i ce [0] + y$ 的 $p r i ce [i]$ 处……
代码文章来源地址https://www.toymoban.com/news/detail-467361.html
```
class Solution {
    public int maximumTastiness(int[] price, int k) {
        Arrays.sort(price);
        int n = price.length;
        int l = 0, r = price[n - 1] - price[0];
        int ans = 0;
        while (l <= r){
            int mid = (r + l) / 2;
            if (check(price, mid ,k)){
                ans = mid;
                l = mid + 1;
            }else{
                r = mid - 1;
            }
        }
        return ans;

    }
    public boolean check(int[] price, int m, int k){
        int count = 1;
        int preIndex = 0;
        for (int i = 1; i < price.length; i++){
            if (price[i] - price[preIndex] >= m ){
                count++;
                preIndex = i;
            }
        }
        return count >= k;
    }
}
```
- 复杂度
  - 时间复杂度： $O (n l o g (n C))$ ， $n$ 是数组的长度，C是数组中的最大值与最小值的差值。排序需要的时间复杂度为 $O (n l o g n)$ ，二分查找的时间复杂度是 $O (l o g C)$ ，每次二分查找需要判断是否符合条件的时间复杂度为 $O (n)$ ，因此总的时间复杂度为 $O (n l o g (n c))$
  - 空间复杂度： $O (l o g n)$ ，排序所需要的栈空间