礼盒的最大甜蜜度【LC2517】
You are given an array of positive integers price where price[i] denotes the price of the ith candy and a positive integer k.
The store sells baskets of k distinct candies. The tastiness of a candy basket is the smallest absolute difference of the prices of any two candies in the basket.
Return the maximum tastiness of a candy basket.
- 思路：使用二分查找的方式寻找最大甜蜜度
- 本题的单调性为：当**最小甜蜜度【数组中任意两个元素的差值的绝对值的最小值】**越大，糖果的可以选择的种类越小【选取的数组中的元素个数】，因此可以通过二分查找法找到最终答案
将题意转化为：当选取的数量一定时，寻找最小甜蜜度的最大值y ，二分查找的下限为0，上限为数组中最大元素与最小元素的差值/（k-1）
- 实现
- 首先对
price数组进行升序排序
class Solution { public int maximumTastiness(int[] price, int k) { Arrays.sort(price); int n = price.length; int l = 0, r = price[n - 1] - price[0]; int ans = 0; while (l <= r){ int mid = (r + l) / 2; if (check(price, mid ,k)){ ans = mid; l = mid + 1; }else{ r = mid - 1; } } return ans; } public boolean check(int[] price, int m, int k){ int count = 1; int preIndex = 0; for (int i = 1; i < price.length; i++){ if (price[i] - price[preIndex] >= m ){ count++; preIndex = i; } } return count >= k; } }
