题目：

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

提示：

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

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/maximum-tastiness-of-candy-basket
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路：

看到找最大值的最小值/最小值的最大值就可以想到二分，因为这类问题容易找到单调关系从而进行二分搜索。

本题的单调关系即为: 袋子里的糖果k越多，答案ans会越小（因为绝对差会变小）。

存在单调关系后，就可以用二分搜索了。

在每一步中，对于给定的答案ans，我们检查能否在k步内达到。如果可以的话，说明当前的y并非在袋子中放入k个糖果能够达到的最小值。令right = mid - 1搜索左侧。如果不可以的话，说明当前的y需要至少k+1个糖果才能达到，不符合题意，令right = mid + 1搜索右侧。

代码：

class Solution {
public:// check if current value (sweetness) is valid for k candiesbool check(vector<int>& price, int val, int k) {int count = 1;int preVal = price[0];for (size_t i = 1; i < price.size(); i++) {if (price[i] >= preVal + val) {count++;preVal = price[i];}}return count < k;}// binary searchint maximumTastiness(vector<int>& price, int k) {sort(price.begin(), price.end());int left = 0;int right = price[price.size() - 1] - price[0];int ans = right;while (left <= right) {int mid = left + (right - left) / 2;if (check(price, mid, k)) {right = mid - 1;} else {ans = mid;left = mid + 1;}}return ans;}
};