【Leetcode 每日一题 - 扩展】2517. 礼盒的最大甜蜜度

问题背景

给你一个正整数数组 $price$，其中 $price[i]$ 表示第 $i$ 类糖果的价格，另给你一个正整数 $k$。
商店组合 $k$ 类 不同 糖果打包成礼盒出售。礼盒的 甜蜜度 是礼盒中任意两种糖果 价格 绝对差的最小值。
返回礼盒的 最大 甜蜜度。

数据约束

• $2\le k\le price.length\le 10^5$
• $1\le price[i]\le 10^9$

解题过程

最大化最小值，考虑二分答案。
左端点的闭区间初始值为 $1$，这种情况相当于所有连续整数都选择到，肯定是符合定义的，但是不一定满足最大的要求。
右端点的开区间初始值，若数组长度用 $n$ 来表示，根据 $price[0]+(k-1)\ast tastiness\le price[n-1]$ 可以得到甜蜜度 $tastiness$ 的上界为 $\lfloor \frac{price[n-1]-price[0]}{k-1}+1\rfloor$。
最后确定移动范围的条件，用当前考虑的值实际地进行计算，判断是否满足要求就可以了。

具体实现

class Solution {
    public int maximumTastiness(int[] price, int k) {
        // 注意数组要进行排序，不然不符合二分有序的前提
        Arrays.sort(price);
        // 标准二分框架，相应地修改范围和
        int left = 1;
        int right = (price[price.length - 1] - price[0]) / (k - 1) + 1;
        while (left < right) {
            int mid = left + ((right - left) >>> 1);
            if (check(price, mid) >= k) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        return left - 1;
    }

    // 用当前的甜蜜度，实际计算能够放多少类
    private int check (int[] price, int tastiness) {
        int res = 1;
        int pre = price[0];
        for (int item : price) {
            if (item >= pre + tastiness) {
                res++;
                pre = item;
            }
        }
        return res;
    }
}