礼盒的最大甜蜜度

标签: 数组 二分查找 排序

难度: Medium

给你一个正整数数组 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 。

提示：

  • 2 <= k <= price.length <= 105
  • 1 <= price[i] <= 109

Submission

运行时间: 300 ms

内存: 27.0 MB

class Solution:
    def maximumTastiness(self, price: List[int], k: int) -> int:
        price.sort()

        l = 1
        r = (price[-1] - price[0]) // (k - 1) + 1

        def check(x: int) -> bool:
            cur = price[0]
            cnt = 1

            for p in price:
                if cur + x <= p:
                    cnt += 1
                    cur = p
            
            return cnt >= k

        while l < r:
            mid = l + r >> 1

            if check(mid):
                l = mid + 1
            else:
                r = mid
            
        return l - 1

Explain

该题解采用了排序与二分搜索的方法来求解最大甜蜜度。首先，将糖果价格排序，再通过二分搜索来确定最大的甜蜜度。二分搜索中，检查函数 'check(x)' 用于判断是否存在至少 'k' 种糖果，其价格差至少为 'x'。如果存在，说明甜蜜度可以更高；如果不存在，那么甜蜜度需要降低。通过不断调整 'x' 的值，直到找到最大的满足条件的 'x'。

时间复杂度: O(n log n)

空间复杂度: O(1)

class Solution:
    def maximumTastiness(self, price: List[int], k: int) -> int:
        price.sort()  # 对价格数组进行排序

        # 初始化二分搜索的边界
        l = 1
        r = (price[-1] - price[0]) // (k - 1) + 1

        def check(x: int) -> bool:
            cur = price[0]  # 从最小价格开始
            cnt = 1  # 已选择的糖果种类数

            # 遍历价格数组，尝试选择符合条件的糖果
            for p in price:
                if cur + x <= p:
                    cnt += 1
                    cur = p  # 更新当前价格
            
            return cnt >= k  # 检查是否已足够选择 k 种糖果

        while l < r:
            mid = (l + r) >> 1  # 计算中间值

            if check(mid):  # 如果可以选择更大的甜蜜度
                l = mid + 1
            else:
                r = mid  # 降低甜蜜度的尝试
        
        return l - 1  # 返回最大可能的甜蜜度

Explore

此表达式用于估算最大可能的甜蜜度。基于题目要求选择至少`k`种糖果，且他们的价格差须至少为`x`，最大的`x`出现在价格差最大的两端糖果之间等间隔地选取`k - 1`个糖果时。`(price[-1] - price[0])`给出了价格数组中最大和最小值的差异，将此差异等分为`k - 1`份，每份的大小即为理论上可能的最大`x`值。加`1`是为确保在二分搜索过程中覆盖所有可能的值。

从最小价格开始选择是为了最大化价格间隔。从最小值开始，可以保证在达到所需的糖果种类数量时，所选的糖果价格间隔尽可能大，从而可能达到更高的甜蜜度。如果从最大价格或其他价格开始，可能导致无法选择足够数量的糖果而错过最优解。

在`l < r`的条件下终止搜索是因为，当`l`等于`r`时，搜索空间已经缩小到一个点，进一步的搜索将不再改变结果。此时的`l`（或`r`，因为此时它们相等）表示最后检查的一个潜在的甜蜜度值，通常是上一次检查`mid`值的上界-1，因为它是最后一个使`check(mid)`为`true`的值。

当`check(mid)`返回`true`时，意味着至少存在一个甜蜜度为`mid`的解决方案，但可能有更大的甜蜜度值也满足条件。因此，更新`l`为`mid + 1`是为了探索是否存在更大的满足条件的甜蜜度，从而确保找到最大可能的甜蜜度。如果直接使用`mid`，可能会错过更优的解。