题目描述
思路解析
一句话答案：LeetCode 2517 礼盒的最大甜蜜度用二分答案：甜蜜度越小越容易凑够 k 颗这条单调性，让判定函数排序后贪心数能选几颗，二分出最大可行甜蜜度，时间 O(n·log C)、空间 O(1)。
从一堆糖果里挑 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 的糖果、答案偏小，得用不小于。
▶ 动画逐步走查（文字版）——想跟着上方动画一帧帧对照就展开
记牢:甜蜜度 x 越小越容易凑够 k 个,可行性单调,于是在 0 到 max 减 min 上二分 x。检验一个 x:排序后贪心,差不小于 x 就选,选够 k 颗即可达,可达就把左界收到 mid、否则右界降到 mid 减 1。二分的是甜蜜度值,不是下标。
总览 · 原始价格还没排序：先看清画面。上面这排是原始价格 8,1,5,3,顺序是乱的。我们要从这 4 类里挑 3 类,让盒中两两价差里最小的那个尽量大。右边面板记三件事:甜蜜度的候选范围、当前正在检验的甜蜜度 x、已经选中的糖果数,现在都还没开始。思路不是硬挑,而是二分猜一个甜蜜度 x,再验证它凑不凑得够 3 颗。
排序 · 从小到大排好：第一步先排序,把 8,1,5,3 排成从小到大的 1,3,5,8。为什么必须排序,因为等会儿的贪心是从最小的价格出发、一路往大走,只有有序才能保证「每次尽量早选、给后面留空间」这套贪心成立。排好之后,数轴上这四颗糖果就均匀铺开了,后面所有操作都在这排有序价格上做。
定范围 · 在 0 到 7 上二分甜蜜度：框定答案范围。甜蜜度最小能到 0,比如有两颗价格一样时最小差就是 0;最大不会超过最贵和最便宜之差,也就是 8 减 1 等于 7。所以答案一定落在 0 到 7 这个闭区间里。接下来不逐个试,而是二分:取中点当候选甜蜜度 x,验证「能不能选出 3 颗,让它们两两差都不小于 x」。请记住,右边面板里动的是甜蜜度 x 的范围,数组这排糖果始终不动。
第一轮 · 取中点 x = 4：开始第一轮二分。当前范围 0 到 7,取中点,x 等于 0 加 7 加 1 再整除 2 得 4。注意这里取中点特意加了个 1、往上取整,这是「可达就把左界收到 mid」那一支必须的防死循环写法。这一轮就问:能不能选出 3 颗糖果,让它们两两差都不小于 4?下面从最小的糖果开始逐颗贪心地挑。
第一轮 · 看价格 1 · 选：贪心从最小的 1 开始。这里有个巧劲:把上一次选中的价格 pre 初始设成负的 x,也就是 -4,这样 1 减去 -4 等于 5,一定不小于 4,所以最小的这颗必被选中。选它,已选记 1 颗,把 pre 更新成 1。道理是:最便宜的糖果留着没意义,越早选、越能给后面腾出价格空间。
第一轮 · 看价格 3 · 跳：看价格 3,它减去上一次选中的 1 等于 2。这个差小于门槛 4,离上一颗太近,选了会拉低最小差,跳过它,继续看下一颗。
第一轮 · 看价格 5 · 选：看价格 5,它减去上一次选中的 1 等于 4。这个差不小于门槛 4,说明它离上一颗够远,选进礼盒,已选变成 2 颗,pre 更新成 5。
第一轮 · 看价格 8 · 跳：看价格 8,它减去上一次选中的 5 等于 3。这个差小于门槛 4,离上一颗太近,选了会拉低最小差,跳过它,继续看下一颗。
第一轮 · x = 4 不可达：一趟贪心扫完,只选到 2 颗,不够 3 颗,说明甜蜜度定到 4 太苛刻,糖果被门槛卡得太狠、凑不齐。那 4 以及更大的都不行,把右界降到 3,范围变成 0 到 3,往更小里找。
第二轮 · 取中点 x = 2：第二轮二分。上一轮把范围收到了 [0, 3],取中点得到候选甜蜜度 x 等于 2。同样问一句:能不能选出 3 颗,让两两差都不小于 2?贪心从最小的糖果往上挑。
第二轮 · 看价格 1 · 选：贪心从最小的 1 开始。这里有个巧劲:把上一次选中的价格 pre 初始设成负的 x,也就是 -2,这样 1 减去 -2 等于 3,一定不小于 2,所以最小的这颗必被选中。选它,已选记 1 颗,把 pre 更新成 1。
第二轮 · 看价格 3 · 选：看价格 3,它减去上一次选中的 1 等于 2。这个差不小于门槛 2,说明它离上一颗够远,选进礼盒,已选变成 2 颗,pre 更新成 3。
第二轮 · 看价格 5 · 选：看价格 5,它减去上一次选中的 3 等于 2。这个差不小于门槛 2,说明它离上一颗够远,选进礼盒,已选变成 3 颗,pre 更新成 5。
第二轮 · 看价格 8 · 选：看价格 8,它减去上一次选中的 5 等于 3。这个差不小于门槛 2,说明它离上一颗够远,选进礼盒,已选变成 4 颗,pre 更新成 8。
第二轮 · x = 2 可达：一趟贪心扫完,选够了 4 颗,不小于要求的 3 颗,说明甜蜜度做到 2 是办得到的。既然 2 能到,那更大的甜蜜度值得一试,把左界收到 2,范围变成 2 到 3。注意 2 本身可能就是答案,所以左界取 2 而不是 2 加 1,继续往更大里试。
第三轮 · 取中点 x = 3：第三轮二分。上一轮把范围收到了 [2, 3],取中点得到候选甜蜜度 x 等于 3。同样问一句:能不能选出 3 颗,让两两差都不小于 3?贪心从最小的糖果往上挑。
第三轮 · 看价格 1 · 选：贪心从最小的 1 开始。这里有个巧劲:把上一次选中的价格 pre 初始设成负的 x,也就是 -3,这样 1 减去 -3 等于 4,一定不小于 3,所以最小的这颗必被选中。选它,已选记 1 颗,把 pre 更新成 1。
第三轮 · 看价格 3 · 跳：看价格 3,它减去上一次选中的 1 等于 2。这个差小于门槛 3,离上一颗太近,选了会拉低最小差,跳过它,继续看下一颗。
第三轮 · 看价格 5 · 选：看价格 5,它减去上一次选中的 1 等于 4。这个差不小于门槛 3,说明它离上一颗够远,选进礼盒,已选变成 2 颗,pre 更新成 5。
第三轮 · 看价格 8 · 选：看价格 8,它减去上一次选中的 5 等于 3。这个差不小于门槛 3,说明它离上一颗够远,选进礼盒,已选变成 3 颗,pre 更新成 8。
第三轮 · x = 3 可达：一趟贪心扫完,选够了 3 颗,不小于要求的 3 颗,说明甜蜜度做到 3 是办得到的。把左界收到 3,范围变成 3 到 3。左右界撞到一块儿了,二分到这一步就该收束了。
收束 · 左右界重合于 3：二分收束了。左界和右界都停在 3,说明 3 是能达到的最大甜蜜度:它可达,而比它大的 4 已经验证过办不到。回看这颗最优选择,贪心选出的正是价格 1、5、8 这三类,它们两两差里最小的正好是 3。
完成 · 最大甜蜜度 = 3：收个尾。这道题的巧劲在于把「怎么选 k 类糖果」这个难题,翻译成「甜蜜度能不能达到 x」这个好答的判断题,再靠单调性二分甜蜜度。price 排序成 1,3,5,8、k = 3,我们只检验了 4、2、3 这 3 个候选,就锁定最大甜蜜度是 3。二分把候选个数从线性压成对数级,每次贪心检查线性扫一遍糖果,又快又稳。
边界:全相等时甜蜜度只能是 0;有重复价格排序后照选,最大差就是答案;题面例子 1,2,5,8,13,21 选 3 颗,最大甜蜜度 8。都能用「排序加贪心」的可行性检查验证。
面试重点:甜蜜度门槛越低越容易选够 k 颗,可行性单调所以能二分;检验用排序加贪心、能选就选,靠交换论证最优;求最大可达值要用 (lo+hi+1) 右移配 lo = mid,防止死循环。
参考代码
from __future__ import annotationsfrom 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复杂度
- 时间：O(n log n + n log C)，n 是糖果类数,C 是价格跨度 max 减 min。先排序是 O(n log n);二分甜蜜度在 0 到 C 上进行,最多 log C 轮,每轮做一次贪心检查、线性扫一遍 n 个价格,是 O(n),合起来 O(n log C)。两部分相加即总时间。演示里 n 等于 4、C 等于 7,排序后只检验了 3 个候选甜蜜度就收敛
- 空间：O(1)，按峰值算,只计排序之外的额外空间。二分与贪心只用了 lo、hi、mid、cnt、pre 这几个标量,不随规模增长,没有开新数组。若把排序自身的栈开销也算进去,C++ 与 Java 约 O(log n)、Python 的 sort 最坏 O(n);检查逻辑本身是常数额外空间 O(1)
易错点
面试追问把动画讲成自己的话
追问为什么甜蜜度可以拿来二分?单调性体现在哪?
追问检验一个 x 时,为什么贪心地「能选就选」是对的?
追问二分为什么用 (lo+hi+1) 右移、可达时又写 lo = mid?
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
从一个范围内选择最多整数 I
LeetCode 2554 · 中等 · 沿着 二分套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题