Leetcode 2517. 礼盒的最大甜蜜度-526互联

题目：

给你一个正整数数组 price ，其中 price[i] 表示第 i 类糖果的价格，另给你一个正整数 k 。

商店组合 k 类不同糖果打包成礼盒出售。礼盒的 甜蜜度 是礼盒中任意两种糖果价格绝对差的最小值。

返回礼盒的最大甜蜜度。

难度：中等

示例1：

输入：price = [13,5,1,8,21,2], k = 3
输出：8
解释：选出价格分别为 [13,5,21] 的三类糖果。
礼盒的甜蜜度为 min(|13 - 5|, |13 - 21|, |5 - 21|) = min(8, 8, 16) = 8 。
可以证明能够取得的最大甜蜜度就是 8 。

示例2：

输入：price = [1,3,1], k = 2
输出：2
解释：选出价格分别为 [1,3] 的两类糖果。 
礼盒的甜蜜度为 min(|1 - 3|) = min(2) = 2 。
可以证明能够取得的最大甜蜜度就是 2 。

示例3：

输入：price = [7,7,7,7], k = 2
输出：0
解释：从现有的糖果中任选两类糖果，甜蜜度都会是 0 。

提示：

2 <= k <= price.length <= 105
1 <= price[i] <= 109

代码实现：

class Solution {
public:
    int maximumTastiness(vector<int>& price, int k) {
        
        sort(price.begin(), price.end());   // 排序
        int n = price.size();
        int lv = 0, rv = price[n - 1] - price[0];   // 最大差值

        // check 用于检查 是否存在至少 k 个数字 满足最小差值至少为 mid
        // auto check = [&](int diff){
        //     int cnt = 1;        // prcie[0] 算1个数 cnt 从1开始
        //     for(int i = 0, j; i < n && cnt <= k; i = j){
        //         j = lower_bound(price.begin() + i + 1, price.end(), price[i] + diff) - price.begin();
        //         cnt += (j != n);    // 如果j != n 说明找到一个数与p[0] 差值至少为mid，则继续往后找
        //     }
        //     return cnt >= k;
        // };

        auto check = [&](int diff){
            int idx = 0;
            int cnt = 1;
            for(int i = 1; i < n; ++i){
                if(price[i] - price[idx] >= diff){
                    ++cnt;
                    idx = i;
                }
            }
            return cnt >= k;
        };

        int res = -1;
        while(lv <= rv){
            int mid = lv + ((rv - lv) >> 1);   // 以 mid 为礼盒甜蜜度
            if(check(mid)){
                res = mid;
                lv = mid + 1;
            }else{
                rv = mid - 1;
            }
        }
        return res;
    }
};