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 <= 10^5
  • 1 <= price[i] <= 10^9

解题思路

解题思路

这道题要求我们从糖果中选择 k 个，使得任意两个糖果价格的最小差值最大。这是一个典型的"最大化最小值"问题，可以使用二分搜索 + 贪心的方法解决。

核心思路

  1. 排序：首先对价格数组进行排序，这样相邻元素的差值就是局部最小的差值。

  2. 二分搜索：在可能的甜美度范围 [0, max(price) - min(price)] 上进行二分搜索，寻找最大的可行甜美度。

  3. 贪心验证：对于给定的甜美度 x，使用贪心策略验证是否能选出 k 个糖果：

    • 从最小价格开始选择第一个糖果
    • 依次向后遍历，如果当前糖果与上一个选中糖果的价格差 ≥ x，则选择当前糖果
    • 如果能选出 k 个糖果，说明甜美度 x 是可行的

算法流程

  1. 对价格数组排序
  2. 设置二分搜索的左右边界：left = 0, right = price[n-1] - price[0]
  3. 在 [left, right] 范围内二分搜索最大可行甜美度
  4. 对每个中间值使用贪心策略验证可行性

时间复杂度主要来自排序 O(n log n) 和二分搜索过程 O(n log(max_price))。

代码实现

class Solution {
public:
    int maximumTastiness(vector<int>& price, int k) {
        sort(price.begin(), price.end());
        int n = price.size();
        
        int left = 0, right = price[n-1] - price[0];
        int result = 0;
        
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (canAchieveTastiness(price, k, mid)) {
                result = mid;
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        
        return result;
    }
    
private:
    bool canAchieveTastiness(const vector<int>& price, int k, int target) {
        int count = 1;
        int lastPicked = price[0];
        
        for (int i = 1; i < price.size(); i++) {
            if (price[i] - lastPicked >= target) {
                count++;
                lastPicked = price[i];
                if (count == k) return true;
            }
        }
        
        return count >= k;
    }
};

class Solution:
    def maximumTastiness(self, price: List[int], k: int) -> int:
        price.sort()
        n = len(price)
        
        def can_achieve_tastiness(target):
            count = 1
            last_picked = price[0]
            
            for i in range(1, n):
                if price[i] - last_picked >= target:
                    count += 1
                    last_picked = price[i]
                    if count == k:
                        return True
            
            return count >= k
        
        left, right = 0, price[n-1] - price[0]
        result = 0
        
        while left <= right:
            mid = (left + right) // 2
            if can_achieve_tastiness(mid):
                result = mid
                left = mid + 1
            else:
                right = mid - 1
        
        return result

public class Solution {
    public int MaximumTastiness(int[] price, int k) {
        Array.Sort(price);
        int n = price.Length;
        
        int left = 0, right = price[n-1] - price[0];
        int result = 0;
        
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (CanAchieveTastiness(price, k, mid)) {
                result = mid;
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        
        return result;
    }
    
    private bool CanAchieveTastiness(int[] price, int k, int target) {
        int count = 1;
        int lastPicked = price[0];
        
        for (int i = 1; i < price.Length; i++) {
            if (price[i] - lastPicked >= target) {
                count++;
                lastPicked = price[i];
                if (count == k) return true;
            }
        }
        
        return count >= k;
    }
}

/**
 * @param {number[]} price
 * @param {number} k
 * @return {number}
 */
var maximumTastiness = function(price, k) {
    price.sort((a, b) => a - b);
    
    const canAchieveTastiness = (minDiff) => {
        let count = 1;
        let lastPrice = price[0];
        
        for (let i = 1; i < price.length; i++) {
            if (price[i] - lastPrice >= minDiff) {
                count++;
                lastPrice = price[i];
                if (count === k) return true;
            }
        }
        return false;
    };
    
    let left = 0;
    let right = price[price.length - 1] - price[0];
    let result = 0;
    
    while (left <= right) {
        const mid = Math.floor((left + right) / 2);
        
        if (canAchieveTastiness(mid)) {
            result = mid;
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n log n + n log(max_price))排序需要 O(n log n)，二分搜索需要 O(log(max_price)) 次，每次验证需要 O(n)
空间复杂度O(1)只使用常数额外空间（不考虑排序的空间）

相关题目