礼盒的最大甜蜜度 图解题解

从一堆糖果里挑 k 类，甜蜜度求的是哪个数

给价格数组 price（每个数是一类糖果的价格）和正整数 k，从中挑 k 类不同糖果装礼盒。甜蜜度是盒里任意两类价格差绝对值中最小的那个，求精挑后它最大能到多少。题面 price=[13,5,1,8,21,2]、k 取 3 时答案是 8：选 1、13、21，两两差里最小的正好是 8，再大就凑不出三类。

把 0 到最大差的每个甜蜜度都试一遍，要试到什么地步

甜蜜度最小是 0（两类价格相同时最小差为 0），最大不超过最贵减最便宜，这里 21-1=20。一个直接想法是从 0 到 20 逐个试，每个都检查能不能挑出 k 类让两两差都够。可最坏要把整段值域（一个量所有可能取值的范围）扫满，值域大到 10⁹ 就跑不动。

甜蜜度这个答案，凭什么能拿来二分

把候选甜蜜度 x 从小到大排开，只问「能不能挑出 k 类、让两两差都不小于 x」。x 越小门槛越松越容易凑够 k 类，x 越大越难凑。于是 x 被切成两段——小的凑得够、大的凑不够，答案就是最大的那个凑得够的 x。这种「能不能达到 x」随 x 单调变化，就能在答案范围里二分：猜一个甜蜜度、验证、再收缩。二分的是甜蜜度值，不是下标。

检查一个甜蜜度能不能达到，贪心该怎么数

把「行不行」做成判定函数 check(x)（输入甜蜜度、答能否凑够 k 类）。先给 price 排序——排好后相邻两颗的差才是能出现的最小间隔，贪心才能从最小价一路往大走：记上次选中的 pre、已选数 cnt，cur 减 pre 不小于 x 就选、cnt 加一、pre 换成 cur，否则跳过，扫完 cnt≥k 即 x 可达。pre 初设 -x，保证最小那颗入选。

二分区间 [lo, hi]，lo=0、hi=max-min，mid=(lo+hi+1)//2：可达就把 lo 收到 mid（可能正是答案、得留），不可达就 hi 降到 mid-1，缩到 lo 与 hi 撞上即答案。

题面那组价格选三类，一轮轮夹出答案

排序后 price=[1,2,5,8,13,21]，lo=0、hi=20。第一轮 mid=(0+20+1)//2=10，从 pre=-10 起选 1、13（差 12），其余离上颗太近全跳，只 2 类不可达，hi 降到 9。第二轮 mid=5，选到 1、8、13、21 四类可达，lo 收到 5。第三、四轮 mid=7、8 各选出 3 类都可达，lo 依次收到 7、8。第五轮 mid=9 只选 1、13 两类不可达，hi 降到 8。lo=hi=8，返回 8。

mid 不加那个 1，只差一格时就永远缩不动

排序 O(n log n)，二分甜蜜度最多 log C 轮（C=max-min）、每轮贪心扫 n 个价，合起来 O(n log n + n·log C)，空间 O(1)。最容易栽的是死循环：mid 写 (lo+hi)//2、可达又写 lo=mid，hi 只比 lo 大一格时 mid 仍算成 lo、范围缩不动，所以这支 mid 必须往上取整成 (lo+hi+1)//2。另一个坑是门槛写成 cur-pre 严格大于 x，会漏掉差恰好等于 x 的糖果、答案偏小，得用不小于。

Python

from __future__ import annotations
from typing import *
from collections import *
from functools import *
from itertools import *
from math import *
from heapq import *
from bisect import *
class Solution:
    def maximumTastiness(self, price: List[int], k: int) -> int:
        def check(x: int) -> bool:
            cnt, pre = 0, -x
            for cur in price:
                if cur - pre >= x:
                    pre = cur
                    cnt += 1
            return cnt >= k

        price.sort()
        l, r = 0, price[-1] - price[0]
        while l < r:
            mid = (l + r + 1) >> 1
            if check(mid):
                l = mid
            else:
                r = mid - 1
        return l

C++

#include <algorithm>
#include <array>
#include <cctype>
#include <climits>
#include <cmath>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
class Solution {
public:
    int maximumTastiness(vector<int>& price, int k) {
        sort(price.begin(), price.end());
        int l = 0, r = price.back() - price[0];
        auto check = [&](int x) -> bool {
            int cnt = 0, pre = -x;
            for (int& cur : price) {
                if (cur - pre >= x) {
                    pre = cur;
                    ++cnt;
                }
            }
            return cnt >= k;
        };
        while (l < r) {
            int mid = (l + r + 1) >> 1;
            if (check(mid)) {
                l = mid;
            } else {
                r = mid - 1;
            }
        }
        return l;
    }
};

Java

import java.util.*;
class Solution {
    public int maximumTastiness(int[] price, int k) {
        Arrays.sort(price);
        int l = 0, r = price[price.length - 1] - price[0];
        while (l < r) {
            int mid = (l + r + 1) >> 1;
            if (check(price, k, mid)) {
                l = mid;
            } else {
                r = mid - 1;
            }
        }
        return l;
    }

    private boolean check(int[] price, int k, int x) {
        int cnt = 0, pre = -x;
        for (int cur : price) {
            if (cur - pre >= x) {
                pre = cur;
                ++cnt;
            }
        }
        return cnt >= k;
    }
}