2517. 最大甜蜜度

LC每日一题，参考2517. 最大甜蜜度。

题目

给你一个正整数数组 price ，其中 price[i] 表示第 i 类糖果的价格，另给你一个正整数 k 。

商店组合 k 类 不同 糖果打包成礼盒出售。礼盒的 甜蜜度 是礼盒中任意两种糖果 价格 绝对差的最小值。

返回礼盒的 最大 甜蜜度。

输入：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 。
输入：price = [1,3,1], k = 2
输出：2
解释：选出价格分别为 [1,3] 的两类糖果。 
礼盒的甜蜜度为 min(|1 - 3|) = min(2) = 2 。
可以证明能够取得的最大甜蜜度就是 2 。
输入：price = [7,7,7,7], k = 2
输出：0
解释：从现有的糖果中任选两类糖果，甜蜜度都会是 0 。

解题思路

• 排序+二分查找：首先肯定要排序,考虑贪心或二分,二分查找的话找指定甜蜜度,范围为[0,price[n-1]-price[0] ],每次找中间值判断是否能找到满足条件的糖果数。

二分查找

class Solution {
    public int maximumTastiness(int[] price, int k) {
        Arrays.sort(price); //排序后糖果下标改变不影响结果
        //逆向思维 二分查找甜蜜度 检查是否能找到k个满足甜蜜度要求的糖果
        int left = 0,right = price[price.length-1] - price[0];
        while(left <= right) {
            int mid = (left + right) >> 1;
            if(check(price,k-1,mid)) left = mid + 1;
            else right = mid - 1;
        }
        return right;
    }
    boolean check(int[] price,int k,int ans) {
        for(int i = 1,pre = price[0]; i < price.length; i++) {
            if(price[i]-pre >= ans) {
                pre = price[i];
                if(--k == 0) return true;
            }
        }
        return false;
    }
}

复杂度分析

• 时间复杂度：O(nlogn + nlogC)，排序nlogn,二分次数logC,C为最大甜蜜度,二分每次检查是否满足需要n,所以二分时间为nlogC。
• 空间复杂度：O(nlogn),n为price数组长度,为排序需要的空间。