当前位置：首页 > article >正文

LeetCode 2517礼盒的最大甜蜜度

article 2025/3/23 1:36:41

🍬 礼盒的最大甜蜜度：二分查找 + 贪心算法详解

📌 题目描述

给定正整数数组 price（第 i 类糖果价格）和正整数 k，商店将 k 类不同糖果打包成礼盒。礼盒的甜蜜度是礼盒中任意两种糖果价格绝对差的最小值。求礼盒的最大甜蜜度。

💡 示例：
输入：price = [1,3,5,7], k = 3
输出：2
解释：选 [1,3,5] 或 [3,5,7]，最小差均为 2，是最大可能值。

🧠 核心思路：最大化最小值问题

这类问题的典型解法是 二分查找（Binary Search），核心步骤：

排序数组：方便计算元素间的差值。
二分甜蜜度：在可能的甜蜜度范围内（0 到最大差）搜索最大值。
贪心验证可行性：对每个中间值，检查是否能选出 k 个数满足最小差≥当前值。

🔍 算法步骤详解

1. 排序数组

Arrays.sort(price); // 升序排列，如[1,3,5,7]

排序后，元素间的差值更容易处理，且贪心选择时只需考虑相邻元素。

2. 二分查找甜蜜度

int left = 0, right = price[price.length-1] - price[0];
while (left < right) {
    int mid = (left + right + 1) / 2; // 向上取整避免死循环
    if (canChoose(price, k, mid)) {
        left = mid; // 可行，尝试更大的甜蜜度
    } else {
        right = mid - 1; // 不可行，尝试更小的甜蜜度
    }
}
return left; // 最终left==right，即最大可行甜蜜度

搜索范围：[0, 最大差]（如示例中 0 到 6）。
关键点：mid=(left+right+1)/2 向上取整，确保每次迭代至少缩小范围（避免left=1, right=2时陷入死循环）。

3. 贪心验证可行性（核心函数）

private boolean canChoose(int[] price, int k, int tastiness) {
    int count = 1; // 初始选第一个元素
    int prev = price[0]; // 记录上一个选中的元素
    for (int i = 1; i < price.length; i++) {
        if (price[i] - prev >= tastiness) { // 当前元素与上一个的差≥tastiness
            count++; // 选中当前元素
            prev = price[i]; // 更新上一个元素
            if (count >= k) return true; // 提前返回
        }
    }
    return count >= k; // 最终是否满足数量
}

贪心策略：每次选离当前元素最近的满足条件的元素，确保选出最多的元素。
原理：排序后，相邻选中元素的差≥tastiness → 所有选中元素的差的最小值≥tastiness。

🚀 完整代码（Java）

import java.util.Arrays;

class Solution {
    public int maximumTastiness(int[] price, int k) {
        Arrays.sort(price); // 排序是关键第一步
        int left = 0, right = price[price.length - 1] - price[0];
        while (left < right) {
            int mid = (left + right + 1) / 2; // 向上取整
            if (canChoose(price, k, mid)) {
                left = mid; // 可行，搜索右半部分
            } else {
                right = mid - 1; // 不可行，搜索左半部分
            }
        }
        return left;
    }

    private boolean canChoose(int[] price, int k, int tastiness) {
        int count = 1; // 至少选1个（第一个元素）
        int prev = price[0];
        for (int num : price) { // 遍历每个元素（从第二个开始）
            if (num - prev >= tastiness) { // 满足最小差条件
                count++;
                prev = num; // 更新上一个选中的元素
                if (count >= k) return true; // 提前终止
            }
        }
        return count >= k; // 检查是否选够k个
    }
}

📊 复杂度分析

操作	时间复杂度	说明
排序	O(n log n)	快速排序的平均时间复杂度
二分查找	O(log m)	m 是价格最大值与最小值的差
每次贪心验证	O(n)	遍历数组一次
总时间复杂度	O(n log n)	排序是主导操作
空间复杂度	O(log n)	排序的栈空间（取决于语言实现）

🌰 示例解析（price=[1,3,5,7], k=3）

排序后：[1,3,5,7]
二分过程：
- 初始：left=0, right=6（7-1=6）
- mid=3（(0+6+1)/2=3.5→3）：
  - 验证：选 1→下一个≥4（1+3）→5（差 4≥3），count=2；下一个≥8→无。count=2<3→不可行→right=2。
- mid=1（(0+2+1)/2=1.5→1）：
  - 验证：选 1→3（差 2≥1），count=2；5（差 2≥1），count=3≥3→可行→left=1。
- mid=2（(1+2+1)/2=2）：
  - 验证：选 1→3（差 2），count=2；5（差 2），count=3≥3→可行→left=2。
- 结束：left==right=2→返回 2（正确）。