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. 总结

本题通过对糖果价格数组排序，并利用二分查找和贪心策略来最大化糖果礼盒的甜蜜度。这个解法不仅高效，还能通过二分查找不断逼近最优解，从而找到最大的甜蜜度。