🍬 礼盒的最大甜蜜度：二分查找 + 贪心算法详解
📌 题目描述
给定正整数数组 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) { // 当前元素与上一个的差≥tastinesscount++; // 选中当前元素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（正确）。
💡 关键细节与边界处理
- k=1 的情况：任意选 1 个元素，甜蜜度为 0（无差值）。
- 代码自动处理：
canChoose初始 count=1，直接返回 true。
- 代码自动处理：
- 所有元素相同：甜蜜度为 0（差均为 0）。
- 向上取整的原因：避免死循环（如 left=1, right=2 时，mid=(1+2)/2=1→进入死循环）。
🎯 同类问题扩展
- 经典问题：《放置花朵最大化最小距离》《分割数组的最大值》。
- 通用解法：最大化最小值问题 → 二分查找 + 贪心 / 二分答案。
📝 总结
- 排序：为贪心选择提供有序基础。
- 二分查找：在可能的甜蜜度范围内高效搜索最大值。
- 贪心验证：用 “每次选最近满足条件的元素” 策略，快速判断可行性。
这种方法的时间复杂度低（主导为排序的 O (n log n)），空间复杂度友好，是解决 “最大化最小值” 问题的标准解法。通过本题，读者可以掌握二分查找与贪心算法的结合技巧，举一反三解决类似问题。
✨ 代码优化点：
- 贪心函数中使用增强 for 循环（
for (int num : price)）提升可读性。- 提前终止循环（
if (count >= k) return true）减少不必要的遍历。
如果有任何疑问或想进一步探讨，欢迎在评论区留言！ 😊
