class Solution {
public:
int maximumTastiness(vector<int>& price, int k) {
}
};
2517. 礼盒的最大甜蜜度
给你一个正整数数组 price ，其中 price[i] 表示第 i 类糖果的价格，另给你一个正整数 k 。
商店组合 k 类 不同 糖果打包成礼盒出售。礼盒的 甜蜜度 是礼盒中任意两种糖果 价格 绝对差的最小值。
返回礼盒的 最大 甜蜜度。
示例 1：
输入：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 。
示例 2：
输入：price = [1,3,1], k = 2 输出：2 解释：选出价格分别为 [1,3] 的两类糖果。 礼盒的甜蜜度为 min(|1 - 3|) = min(2) = 2 。 可以证明能够取得的最大甜蜜度就是 2 。
示例 3：
输入：price = [7,7,7,7], k = 2 输出：0 解释：从现有的糖果中任选两类糖果，甜蜜度都会是 0 。
提示：
1 <= price.length <= 1051 <= price[i] <= 1092 <= k <= price.length原站题解
golang 解法, 执行用时: 136 ms, 内存消耗: 8.6 MB, 提交时间: 2023-01-03 11:40:13
func maximumTastiness(price []int, k int) int {
sort.Ints(price)
return sort.Search((price[len(price)-1]-price[0])/(k-1), func(d int) bool {
d++
cnt, x0 := 1, price[0]
for _, x := range price[1:] {
if x >= x0+d {
cnt++
x0 = x
}
}
return cnt < k
})
}
python3 解法, 执行用时: 436 ms, 内存消耗: 23.4 MB, 提交时间: 2023-01-03 11:39:28
class Solution:
def maximumTastiness(self, price: List[int], k: int) -> int:
price.sort()
def check(d: int) -> bool:
cnt, x0 = 1, price[0]
for x in price:
if x >= x0 + d:
cnt += 1
x0 = x
return cnt >= k
left, right = 0, (price[-1] - price[0]) // (k - 1) + 1 # 开区间
while left + 1 < right:
mid = (left + right) // 2
if check(mid): left = mid
else: right = mid
return left