题目： 2571 礼盒的最大甜蜜度

题面

给你一个正整数数组 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 。

Tips

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

Code

代码解释

这段 C++ 代码旨在解决一个优化问题：在给定的价格数组 price 中选择 k 个不同的价格，使得这些价格之间的最小差值最大化。为了解决这个问题，代码采用了二分查找算法。通过二分查找确定可以达到的最大最小差值，并通过遍历数组检查是否可以选择 k 个价格，使得它们之间的差值至少为这个值。

原始代码

class Solution {
public:
    Solution(){
        ios::sync_with_stdio(0);
        cin.tie(0);
        cout.tie(0);
    }
    int maximumTastiness(vector<int>& price, int k) {
        sort(price.begin(), price.end());
        int n = price.size();
        int l = 1, r = price[n - 1] - price[0];

        while(l <= r){
            int mid = l + (r - l) / 2;
            int cnt = 1;
            int pre = price[0];
            for(int i = 1; i < n; i++){
                if(price[i]>= pre + mid){
                    cnt++;
                    pre = price[i];
                }
            }
            if(cnt >= k) l = mid + 1;
            else r = mid - 1;
        }
        return r;
    }
};

逐行解释

1 2	class Solution { public:

这是 Solution 类的定义开始。这个类封装了解决问题的方法。

Solution(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
}

这是 Solution 类的构造函数，用来优化输入和输出的效率。这一部分代码通过禁用 C++ 标准输入输出与 C 标准输入输出的同步，加快了程序的执行速度，特别是在涉及大量 I/O 操作时。

1	int maximumTastiness(vector<int>& price, int k) {

这是 maximumTastiness 函数的定义。它接受一个整数向量 price 作为参数，表示一组价格，并且接受一个整数 k，表示需要选择的价格数量。函数返回一个整数值，即最大化的最小差值。

1	sort(price.begin(), price.end());

这一行对 price 向量进行排序。通过排序，能够方便地找到具有最大最小差值的价格组合。

1	int n = price.size();

获取 price 向量的大小，并将其存储在变量 n 中。

1	int l = 1, r = price[n - 1] - price[0];

定义 l 和 r 作为二分查找的左右边界。l 初始化为 1，r 初始化为 price 向量中的最大值与最小值的差值。这是可能的最大最小差值。

1 2	while(l <= r){ int mid = l + (r - l) / 2;

进入二分查找循环。mid 表示当前猜测的最小差值，它是左右边界的中点。

1 2	int cnt = 1; int pre = price[0];

初始化 cnt 为 1，用来统计选择的价格数量。pre 变量保存当前选择的价格，初始值为 price[0]。

for(int i = 1; i < n; i++){
    if(price[i]>= pre + mid){
        cnt++;
        pre = price[i];
    }
}

这一段代码遍历 price 数组，从第二个元素开始。对于每个价格，如果它与上一个选择的价格之间的差值大于或等于 mid，则选择这个价格，并更新 cnt 和 pre。

1 2	if(cnt >= k) l = mid + 1; else r = mid - 1;

如果可以选择的价格数量 cnt 大于或等于 k，说明当前的 mid 是可行的，于是将左边界 l 移动到 mid + 1，尝试寻找更大的差值。否则，将右边界 r 移动到 mid - 1。

1
2
3

        return r;
    }
};

最终返回 r，它代表在 k 个选择的价格中，能够实现的最大最小差值。

代码总结

这段代码通过二分查找优化了寻找价格数组中最大化的最小差值的问题。在已经排序的价格数组上，通过二分法确定可以实现的最大最小差值，然后验证能否选择 k 个价格，使它们之间的差值至少为这个值。通过这种方法，代码高效地解决了问题。

时间复杂度：O(n log d)，其中 n 是价格数组的长度，d 是价格数组中最大值与最小值的差值。
空间复杂度：O(1)，因为只使用了常数空间。