2517. 礼盒的最大甜蜜度（Maximum Tastiness of Candy Box）
2517. 礼盒的最大甜蜜度（Maximum Tastiness of Candy Box）
问题描述
给定一个正整数数组 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。
示例 2：
输入：
price = [1,3,1], k = 2
输出：
2
解释：
选出价格分别为 [1, 3] 的两类糖果。礼盒的甜蜜度为 min(|1 - 3|) = min(2) = 2。
示例 3：
输入：
price = [7,7,7,7], k = 2
输出：
0
解释：
从现有的糖果中任选两类糖果，甜蜜度都会是 0。
解题思路
1. 问题分析
我们需要从 price 数组中选择 k 类糖果，这些糖果的甜蜜度是由它们的价格差决定的，而我们需要找到一种选择方法，使得最大甜蜜度尽可能大。
- 甜蜜度的定义：礼盒中任意两种糖果价格的绝对差的最小值。
- 目标：最大化礼盒的最小价格差。
2. 关键观察
- 排序： 将
price数组排序后，糖果的价格差会变得更加规律。因为如果选择相邻的价格差，显然会更小。 - 二分查找： 为了找到最大甜蜜度，我们可以用二分查找来试探不同的甜蜜度，逐渐逼近最优解。
3. 解法步骤
-
排序： 首先对
price数组进行排序，使得选择的糖果价格差最小。 -
二分查找： 设定一个甜蜜度的范围，从
0到price[-1] - price[0]。在此范围内进行二分查找，检查是否可以选出k类糖果，使得它们的最小价格差大于等于当前的mid。 -
贪心选择： 对于每一个候选的甜蜜度
d，我们可以通过贪心算法来选择糖果。遍历价格数组，确保每个新选择的糖果价格与之前选择的糖果价格差不小于d，如果满足条件，则继续选择糖果。
4. 代码实现
from typing import Listclass Solution:def maximumTastiness(self, price: List[int], k: int) -> int:# 辅助函数：判断是否可以选出至少 k 个糖果，且其最小价格差大于等于 ddef f(d: int) -> int:cnt = 1 # 选择第一个糖果pre = price[0] # 上一个选择的糖果的价格for p in price:if p >= pre + d: # 当前糖果价格与前一个糖果价格差 >= dcnt += 1pre = p # 更新上一个选择的糖果return cntprice.sort() # 对价格数组进行排序left = 0 # 二分查找的左边界right = (price[-1] - price[0]) // (k - 1) + 1 # 二分查找的右边界# 二分查找最大甜蜜度while left + 1 < right:mid = (left + right) // 2if f(mid) >= k: # 如果可以选择 k 个糖果，返回 midleft = midelse:right = midreturn left
5. 时间复杂度
- 排序操作的时间复杂度为
O(n log n)，其中n是price数组的长度。 - 二分查找的时间复杂度为
O(log(max_price - min_price))。 - 对每一个中间值
mid，我们需要遍历一次price数组，时间复杂度为O(n)。
因此，总的时间复杂度为 O(n log n + n log(max_price - min_price))，其中 n 是糖果数量，max_price - min_price 是糖果价格的范围。
6. 总结
本题通过对糖果价格数组排序，并利用二分查找和贪心策略来最大化糖果礼盒的甜蜜度。这个解法不仅高效，还能通过二分查找不断逼近最优解，从而找到最大的甜蜜度。