给你一个正整数数组 price ,其中 price[i] 表示第 i 类糖果的价格,另给你一个正整数 k 。
商店组合 k 类 不同 糖果打包成礼盒出售。礼盒的 甜蜜度 是礼盒中任意两种糖果 价格 绝对差的最小值。
返回礼盒的 最大 甜蜜度。
price = [13,5,1,8,21,2], k = 3
price = [1,3,1], k = 2
price = [7,7,7,7], k = 2
8
2
0
答案具有单调性,且n的范围为10510^5105, 只能使用O(nlogn)O(nlogn)O(nlogn),可直接使用二分
class Solution {int[] price;int k;public int maximumTastiness(int[] price, int k) {Arrays.sort(price);this.price = price;this.k = k;int l = 0;int r = price[price.length-1];while(l <= r){int mid = (r + l) / 2;if(!check(mid)) r = mid - 1;else l = mid + 1;}return r;}private boolean check(int x){int ans = 1;int max = price[0];for(int i = 1; i < price.length; i++){if(price[i] >= max + x){max = price[i];ans++;}}return ans >= k;}
}