网站免费虚拟主机申请,dns上国外网站,太原小程序商城制作,威联通WordPress2517. 礼盒的最大甜蜜度#xff08;Maximum Tastiness of Candy Box#xff09;
问题描述
给定一个正整数数组 price#xff0c;其中 price[i] 表示第 i 类糖果的价格#xff0c;另给定一个正整数 k。商店将 k 类不同糖果组合成礼盒出售。礼盒的甜蜜度是礼盒中任意两种糖…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 left5. 时间复杂度
排序操作的时间复杂度为 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. 总结
本题通过对糖果价格数组排序并利用二分查找和贪心策略来最大化糖果礼盒的甜蜜度。这个解法不仅高效还能通过二分查找不断逼近最优解从而找到最大的甜蜜度。
