2517. 礼盒的最大甜蜜度 (opens new window)

1.二分查找+贪心

💡 ​题目含有【最大化最小值】或者是【最小化最大值】，一般都是用二分查找。因为甜蜜度越大，可选择的糖果越少，存在单调关系，保证最大甜蜜度一定在另一边区间，从而通过二分进行逼近。

解题核心有两个需要注意的地方：

• 首先需要对所有礼物盒进行排序，从而保证相邻节点的绝对值之差的最小值，一定是礼盒任意两种糖果价格绝对值差的最小值。如果是乱序的话，则需要两两计算绝对值之差求最小值，总共要算n(n-1)/2次。
• 直观上每次选取符合条件(大于甜蜜度)的礼盒的价格越小，那么后续能够选择的糖果越多(贪心)。

二分的搜索空间是甜蜜度，对于每个甜蜜度，如果当前元素和上一个元素的间隔小于甜蜜度，则当前元素不打包进礼物盒。每次搜索过后统计打包进礼物盒的所有糖果种类：

• 如果糖果种类小于k，则说明当前甜蜜度下不满足题目要求，最大甜蜜度在左半区间
• 如果糖果种类大于等于k，则说明最大甜蜜度在右侧，可以继续缩小窗口区间继续逼近。

class Solution {
    public static int maximumTastiness(int[] price, int k) {
        Arrays.sort(price);
        int left = 0, right = (price[price.length - 1] - price[0])/(k-1);
        int mid = (left + right) / 2;
        int res = 0;
        while (left <= right) {
            mid = (left + right) / 2;
            int step = 1, last = price[0];
            for (int i = 1; i < price.length; i++) {
                if (price[i] - last >= mid) {
                    last = price[i];
                    step++;
                }
            }
            if (step >= k) {
                left = mid + 1;
                res = Math.max(res, mid);
            } else {
                right = mid - 1;
            }
        }
        return res;
    }
}