给你一个正整数数组 price ,其中 price[i] 表示第 i 类糖果的价格,另给你一个正整数 k 。
商店组合 k 类 不同 糖果打包成礼盒出售。礼盒的 甜蜜度 是礼盒中任意两种糖果 价格 绝对差的最小值。
返回礼盒的 最大 甜蜜度。
来源:力扣(LeetCode)
链接:https://leetcode.cn/problems/maximum-tastiness-of-candy-basket
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
二分
import java.util.Arrays;
class Solution {
private boolean canFindK(int[] prices, int val, int k) {
int ans = 1;
int pre = prices[0];
for (int i = 1; i < prices.length; i++) {
if (prices[i] - pre >= val) {
ans++;
pre = prices[i];
}
}
return ans >= k;
}
public int maximumTastiness(int[] price, int k) {
if (price == null || price.length < 2 || k < 2) {
return 0;
}
int ans = 0;
Arrays.sort(price);
int left = 0, right = price[price.length - 1] - price[0];
while (left <= right) {
int mid = (left + right) >> 1;
if (canFindK(price, mid, k)) {
ans = mid;
left = mid + 1;
} else {
right = mid - 1;
}
}
return ans;
}
}