README.md

2517. 礼盒的最大甜蜜度

English Version

题目描述

给你一个正整数数组 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 <= 105
• 1 <= price[i] <= 109
• 2 <= k <= price.length

解法

方法一：二分查找

我们先对数组 price 进行排序，然后二分枚举甜蜜度，找到最大的且满足至少有 $k$ 类糖果的甜蜜度。

时间复杂度 $O(n \times \log M)$，空间复杂度 $O(1)$。其中 $n$ 为数组 price 的长度，而 $M$ 为数组 price 中的最大值。本题中我们取 $M = 10^9$。

Python3

class Solution:
    def maximumTastiness(self, price: List[int], k: int) -> int:
        def check(x):
            cnt = 1
            s = price[0]
            for p in price[1:]:
                if p - s >= x:
                    s = p
                    cnt += 1
            return cnt >= k

        price.sort()
        left, right = 0, 10**9
        while left < right:
            mid = (left + right + 1) >> 1
            if check(mid):
                left = mid
            else:
                right = mid - 1
        return left

Java

class Solution {
    private int[] price;
    private int k;

    public int maximumTastiness(int[] price, int k) {
        Arrays.sort(price);
        this.price = price;
        this.k = k;
        int left = 0, right = 1000000000;
        while (left < right) {
            int mid = (left + right + 1) >> 1;
            if (check(mid)) {
                left = mid;
            } else {
                right = mid - 1;
            }
        }
        return left;
    }

    private boolean check(int x) {
        int s = price[0];
        int cnt = 1;
        for (int i = 1; i < price.length; ++i) {
            if (price[i] - s >= x) {
                s = price[i];
                ++cnt;
            }
        }
        return cnt >= k;
    }
}

C++

class Solution {
public:
    int maximumTastiness(vector<int>& price, int k) {
        sort(price.begin(), price.end());
        int left = 0, right = 1e9;
        auto check = [&](int x) {
            int s = price[0];
            int cnt = 1;
            for (int i = 1; i < price.size(); ++i) {
                if (price[i] - s >= x) {
                    s = price[i];
                    ++cnt;
                }
            }
            return cnt >= k;
        };
        while (left < right) {
            int mid = (left + right + 1) >> 1;
            if (check(mid)) {
                left = mid;
            } else {
                right = mid - 1;
            }
        }
        return left;
    }
};

Go

func maximumTastiness(price []int, k int) int {
	sort.Ints(price)
	check := func(x int) bool {
		s := price[0]
		cnt := 1
		for _, p := range price[1:] {
			if p-s >= x {
				s = p
				cnt++
			}
		}
		return cnt >= k
	}
	left, right := 0, 1000000000
	for left < right {
		mid := (left + right + 1) >> 1
		if check(mid) {
			left = mid
		} else {
			right = mid - 1
		}
	}
	return left
}

...