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

这道题到底在问什么

输入

price=[13,5,1,8,21,2], k=3

输出

8

输入

price=[1,3,1], k=2

输出

2

输入

price=[7,7,7,7], k=2

输出

0

最优解：一步一步想明白

1. 3记牢:甜蜜度 x 越小越容易凑够 k 个,可行性单调,于是在 0 到 max 减 min 上二分 x。检验一个 x:排序后贪心,差不小于 x 就选,选够 k 颗即可达,可达就把左界收到 mid、否则右界降到 mid 减 1。二分的是甜蜜度值,不是下标。
2. 4先看清画面。上面这排是原始价格 8,1,5,3,顺序是乱的。我们要从这 4 类里挑 3 类,让盒中两两价差里最小的那个尽量大。右边面板记三件事:甜蜜度的候选范围、当前正在检验的甜蜜度 x、已经选中的糖果数,现在都还没开始。思路不是硬挑,而是二分猜一个甜蜜度 x,再验证它凑不凑得够 3 颗。
3. 5第一步先排序,把 8,1,5,3 排成从小到大的 1,3,5,8。为什么必须排序,因为等会儿的贪心是从最小的价格出发、一路往大走,只有有序才能保证「每次尽量早选、给后面留空间」这套贪心成立。排好之后,数轴上这四颗糖果就均匀铺开了,后面所有操作都在这排有序价格上做。
4. 6框定答案范围。甜蜜度最小能到 0,比如有两颗价格一样时最小差就是 0;最大不会超过最贵和最便宜之差,也就是 8 减 1 等于 7。所以答案一定落在 0 到 7 这个闭区间里。接下来不逐个试,而是二分:取中点当候选甜蜜度 x,验证「能不能选出 3 颗,让它们两两差都不小于 x」。请记住,右边面板里动的是甜蜜度 x 的范围,数组这排糖果始终不动。
5. 7开始第一轮二分。当前范围 0 到 7,取中点,x 等于 0 加 7 加 1 再整除 2 得 4。注意这里取中点特意加了个 1、往上取整,这是「可达就把左界收到 mid」那一支必须的防死循环写法。这一轮就问:能不能选出 3 颗糖果,让它们两两差都不小于 4?下面从最小的糖果开始逐颗贪心地挑。
6. 8贪心从最小的 1 开始。这里有个巧劲:把上一次选中的价格 pre 初始设成负的 x,也就是 -4,这样 1 减去 -4 等于 5,一定不小于 4,所以最小的这颗必被选中。选它,已选记 1 颗,把 pre 更新成 1。道理是:最便宜的糖果留着没意义,越早选、越能给后面腾出价格空间。
7. 9看价格 3,它减去上一次选中的 1 等于 2。这个差小于门槛 4,离上一颗太近,选了会拉低最小差,跳过它,继续看下一颗。
8. 10看价格 5,它减去上一次选中的 1 等于 4。这个差不小于门槛 4,说明它离上一颗够远,选进礼盒,已选变成 2 颗,pre 更新成 5。
9. 11看价格 8,它减去上一次选中的 5 等于 3。这个差小于门槛 4,离上一颗太近,选了会拉低最小差,跳过它,继续看下一颗。
10. 12一趟贪心扫完,只选到 2 颗,不够 3 颗,说明甜蜜度定到 4 太苛刻,糖果被门槛卡得太狠、凑不齐。那 4 以及更大的都不行,把右界降到 3,范围变成 0 到 3,往更小里找。
11. 13第二轮二分。上一轮把范围收到了 [0, 3],取中点得到候选甜蜜度 x 等于 2。同样问一句:能不能选出 3 颗,让两两差都不小于 2?贪心从最小的糖果往上挑。
12. 14贪心从最小的 1 开始。这里有个巧劲:把上一次选中的价格 pre 初始设成负的 x,也就是 -2,这样 1 减去 -2 等于 3,一定不小于 2,所以最小的这颗必被选中。选它,已选记 1 颗,把 pre 更新成 1。
13. 15看价格 3,它减去上一次选中的 1 等于 2。这个差不小于门槛 2,说明它离上一颗够远,选进礼盒,已选变成 2 颗,pre 更新成 3。
14. 16看价格 5,它减去上一次选中的 3 等于 2。这个差不小于门槛 2,说明它离上一颗够远,选进礼盒,已选变成 3 颗,pre 更新成 5。
15. 17看价格 8,它减去上一次选中的 5 等于 3。这个差不小于门槛 2,说明它离上一颗够远,选进礼盒,已选变成 4 颗,pre 更新成 8。
16. 18一趟贪心扫完,选够了 4 颗,不小于要求的 3 颗,说明甜蜜度做到 2 是办得到的。既然 2 能到,那更大的甜蜜度值得一试,把左界收到 2,范围变成 2 到 3。注意 2 本身可能就是答案,所以左界取 2 而不是 2 加 1,继续往更大里试。
17. 19第三轮二分。上一轮把范围收到了 [2, 3],取中点得到候选甜蜜度 x 等于 3。同样问一句:能不能选出 3 颗,让两两差都不小于 3?贪心从最小的糖果往上挑。
18. 20贪心从最小的 1 开始。这里有个巧劲:把上一次选中的价格 pre 初始设成负的 x,也就是 -3,这样 1 减去 -3 等于 4,一定不小于 3,所以最小的这颗必被选中。选它,已选记 1 颗,把 pre 更新成 1。
19. 21看价格 3,它减去上一次选中的 1 等于 2。这个差小于门槛 3,离上一颗太近,选了会拉低最小差,跳过它,继续看下一颗。
20. 22看价格 5,它减去上一次选中的 1 等于 4。这个差不小于门槛 3,说明它离上一颗够远,选进礼盒,已选变成 2 颗,pre 更新成 5。
21. 23看价格 8,它减去上一次选中的 5 等于 3。这个差不小于门槛 3,说明它离上一颗够远,选进礼盒,已选变成 3 颗,pre 更新成 8。
22. 24一趟贪心扫完,选够了 3 颗,不小于要求的 3 颗,说明甜蜜度做到 3 是办得到的。把左界收到 3,范围变成 3 到 3。左右界撞到一块儿了,二分到这一步就该收束了。
23. 25二分收束了。左界和右界都停在 3,说明 3 是能达到的最大甜蜜度:它可达,而比它大的 4 已经验证过办不到。回看这颗最优选择,贪心选出的正是价格 1、5、8 这三类,它们两两差里最小的正好是 3。
24. 26收个尾。这道题的巧劲在于把「怎么选 k 类糖果」这个难题,翻译成「甜蜜度能不能达到 x」这个好答的判断题,再靠单调性二分甜蜜度。price 排序成 1,3,5,8、k = 3,我们只检验了 4、2、3 这 3 个候选,就锁定最大甜蜜度是 3。二分把候选个数从线性压成对数级,每次贪心检查线性扫一遍糖果,又快又稳。

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

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

#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;
    }
};

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;
    }
}

复杂度

面试官可能追问