LeetCode 2517礼盒的最大甜蜜度

时间：2025-03-24 07:40:19

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

???? 题目描述

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

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

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

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

  1. 排序数组：方便计算元素间的差值。
  2. 二分甜蜜度：在可能的甜蜜度范围内（0 到最大差）搜索最大值。
  3. 贪心验证可行性：对每个中间值，检查是否能选出 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. 排序后：[1,3,5,7]
  2. 二分过程：
    • 初始：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（正确）。

???? 关键细节与边界处理

  1. k=1 的情况：任意选 1 个元素，甜蜜度为 0（无差值）。
    • 代码自动处理：canChoose初始 count=1，直接返回 true。
  2. 所有元素相同：甜蜜度为 0（差均为 0）。
  3. 向上取整的原因：避免死循环（如 left=1, right=2 时，mid=(1+2)/2=1→进入死循环）。

???? 同类问题扩展

  • 经典问题：《放置花朵最大化最小距离》《分割数组的最大值》。
  • 通用解法：最大化最小值问题 → 二分查找 + 贪心 / 二分答案。

???? 总结

  1. 排序：为贪心选择提供有序基础。
  2. 二分查找：在可能的甜蜜度范围内高效搜索最大值。
  3. 贪心验证：用 “每次选最近满足条件的元素” 策略，快速判断可行性。

这种方法的时间复杂度低（主导为排序的 O (n log n)），空间复杂度友好，是解决 “最大化最小值” 问题的标准解法。通过本题，读者可以掌握二分查找与贪心算法的结合技巧，举一反三解决类似问题。

✨ 代码优化点：

 
  • 贪心函数中使用增强 for 循环（for (int num : price)）提升可读性。
  • 提前终止循环（if (count >= k) return true）减少不必要的遍历。

如果有任何疑问或想进一步探讨，欢迎在评论区留言！ ????

相关文章