题目链接：2517. 礼盒的最大甜蜜度
方法：二分
解题思路
- 题目意思：当前有 \(n\) 类糖果，从 \(0\) 到 \(n - 1\) 编号，\(price[i]\) 表示第 \(i\) 类糖果的价格，现要你在其中选择 \(k\) 类不同的糖果，组成一个集合 \(s\)，该集合的值为集合中两种糖果差的绝对值的最小值，现在要求你计算所有可能集合值的最大值；
- 明确几点：
- 要求的是最大值，只是最大值中的“值”为最小值；
- 集合 \(s\) 一定由 \(k\) 类组成，否则没有值；
- 最大值一定在，\([0, max(price) - min(price)]\) 区间内。
- 假设某集合的值为 \(val\)，那么集合中两个元素间的差值一定大于等于 \(val\)，那么若该集合中元素从小到大排列，那么其递增的值大于等于 \(val\)，且集合以 \(min(price)\) 为起点（贪心思想），进行二分查找其下一个可能元素，就可以确定值为 \(val\) 的集合，此时说明当前值 \(val\) 存在，那么其可能的最大值在 \([val, max(price) - min(price)]\) 之间，显然也可以进行二分。
代码
class Solution {
public:
int maximumTastiness(vector<int>& price, int k) {
sort(price.begin(), price.end());
int n = price.size();
int l = 0, r = price[n - 1] - price[0];
while (l < r) {
int mid = l + r + 1 >> 1;
int cnt = 1;
for (int i = 0, idx; i < n; i = idx ) {
idx = lower_bound(price.begin() + i, price.end(), price[i] + mid) - price.begin();
if (idx != n) cnt ++ ;
}
if (cnt >= k) l = mid;
else r = mid - 1;
}
return l;
}
};
复杂度分析
时间复杂度：\(O((n + logU)logn)，U = max(price) - min(price)\)；
空间复杂度：\(O(1)\)，不算排序。