礼盒的最大甜蜜度
难度:
标签:
题目描述
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.
Example 1:
Input: price = [13,5,1,8,21,2], k = 3 Output: 8 Explanation: Choose the candies with the prices [13,5,21]. The tastiness of the candy basket is: min(|13 - 5|, |13 - 21|, |5 - 21|) = min(8, 8, 16) = 8. It can be proven that 8 is the maximum tastiness that can be achieved.
Example 2:
Input: price = [1,3,1], k = 2 Output: 2 Explanation: Choose the candies with the prices [1,3]. The tastiness of the candy basket is: min(|1 - 3|) = min(2) = 2. It can be proven that 2 is the maximum tastiness that can be achieved.
Example 3:
Input: price = [7,7,7,7], k = 2 Output: 0 Explanation: Choosing any two distinct candies from the candies we have will result in a tastiness of 0.
Constraints:
2 <= k <= price.length <= 1051 <= price[i] <= 109
代码结果
运行时间: 300 ms, 内存: 27.0 MB
/*
* 思路：
* 1. 首先对价格数组进行排序。
* 2. 使用二分查找来找到最大甜蜜度，设定左右边界为0和价格数组中的最大差值。
* 3. 对于每一个可能的甜蜜度，使用贪心算法检查是否能够选出k种糖果使得相邻糖果的差值大于等于该甜蜜度。
*/
import java.util.Arrays;
import java.util.stream.IntStream;
public class CandySweetnessStream {
public int maximumSweetness(int[] price, int k) {
Arrays.sort(price);
int left = 0;
int right = IntStream.of(price).max().orElse(0) - IntStream.of(price).min().orElse(0);
int result = 0;
while (left <= right) {
int mid = left + (right - left) / 2;
if (canFormSweetBox(price, k, mid)) {
result = mid;
left = mid + 1;
} else {
right = mid - 1;
}
}
return result;
}
private boolean canFormSweetBox(int[] price, int k, int sweetness) {
int count = 1;
int prev = price[0];
for (int i = 1; i < price.length; i++) {
if (price[i] - prev >= sweetness) {
count++;
prev = price[i];
if (count >= k) {
return true;
}
}
}
return false;
}
public static void main(String[] args) {
CandySweetnessStream solution = new CandySweetnessStream();
int[] price = {13, 5, 1, 8, 21, 2};
int k = 3;
System.out.println(solution.maximumSweetness(price, k)); // 输出: 8
}
}
解释
方法:
该题解采用了排序与二分搜索的方法来求解最大甜蜜度。首先，将糖果价格排序，再通过二分搜索来确定最大的甜蜜度。二分搜索中，检查函数 'check(x)' 用于判断是否存在至少 'k' 种糖果，其价格差至少为 'x'。如果存在，说明甜蜜度可以更高；如果不存在，那么甜蜜度需要降低。通过不断调整 'x' 的值，直到找到最大的满足条件的 'x'。
时间复杂度:
O(n log n)
空间复杂度:
O(1)
代码细节讲解
🦆
为什么要在二分搜索中使用`(price[-1] - price[0]) // (k - 1) + 1`作为右边界r的初始值？这个表达式是如何计算得来的？
▷🦆
在`check(x)`函数中，为什么选择从数组的最小价格开始，而不是从最大价格或其他价格开始？
▷🦆
二分搜索终止条件为`while l < r`，为什么在`l == r`时停止搜索？此时的`l`或`r`是否代表一个有效的甜蜜度值？
▷🦆
当`check(mid)`函数返回`true`时，为什么要将`l`设置为`mid + 1`，而不是直接使用`mid`作为可能的最大甜蜜度？
▷