🔗 🟡 2517. Maximum Tastiness of Candy Basket 2021

tags: `Week Contest 325` `二分搜尋(Binary Search)` `排序(Sorting)`

題意

給定一個正整數陣列 $\text{price}$ ，其中 $\text{price}[i]$ 表示第 $i$ 種糖果的價格，另給定一個正整數 $k$ 。

將 $k$ 種不同種類的糖果放入糖果籃中，糖果籃的 美味程度(tastiness) 是糖果籃中任意兩種糖果的價格差的最小值。

返回糖果籃的最大美味程度。

約束條件

$2 \leq k \leq \text{price.length} \leq 10^5$
$1 \leq \text{price}[i] \leq 10^9$

思路：排序(Sorting) + 二分搜尋(Binary Search)

首先確定思路，美味程度即最大的最小價格差，而要直接計算出最大的美味程度顯然是很困難的，但對於給定的美味程度 $d$ ，我們可以確定是否有 $k$ 顆糖果的價格差都 $\geq d$ ，因此可以使用二分搜尋(Binary Search) 來找到最大的最小價格差。

定義一個函數 check(d) 來檢查是否可以將 $k$ 種不同種類的糖果放入糖果籃中，使得糖果籃的 美味程度(tastiness) 至少為 $d$ 。

使用 $cnt$ 來記錄放置糖果的數量， $pre$ 來記錄前一個糖果的價格。
遍歷 $\text{price}$ $price$ 陣列中的每個元素 $\text{p}$ $p$
- 如果 $\text{p} - \text{pre} \geq d$ ，代表可以放置糖果，則 $cnt$ 加一，並更新 $pre$ 為 $\text{p}$ 。
最後返回 $cnt \geq k$ ，即是否可以放置 $k$ 種不同種類的糖果。

這裡使用左閉右閉區間進行二分搜尋，令 $left = 0$ ， $right = \text{price}[n-1] - \text{price}[0]$ ，在 $[left, right]$ 的範圍內進行二分搜尋，不斷調整左右範圍直到找到最大的最小價格差為止。

根據定義的 check 函數，區間的左側為 $\text{True}$ ，而右側為 $\text{False}$ 。
如果 $\text{check}(mid) = \text{True}$ ，則將左範圍擴大到 $[mid+1, right]$ 。
如果 $\text{check}(mid) = \text{False}$ ，則將右範圍縮小到 $[left, mid-1]$ 。
當區間為空，即 $left > right$ 時，終止搜尋。

最終返回 $right$ ，即最大的最小價格差。

複雜度分析

時間複雜度： $\mathcal{O}(n \log n + n \log M) = \mathcal{O}(n \log (nM))$ $O (n lo g n + n lo g M) = O (n lo g (n M))$ ，其中 $n$ $n$ 為陣列 $\text{price}$ $price$ 的長度， $M$ $M$ 為 $\text{price}$ $price$ 的最大值。
- 對陣列 $\text{price}$ 進行排序需要 $\mathcal{O}(n \log n)$ 時間。
- 需要進行 $\log M$ 次二分搜尋，每次搜尋需要遍歷 $n$ 個元素來檢查是否可以放置 $k$ 種不同種類的糖果。
空間複雜度： $\mathcal{O}(1)$ ，忽略排序的空間複雜度。

class Solution:
    def maximumTastiness(self, price: List[int], k: int) -> int:
        n = len(price)
        price.sort()

        def check(d: int) -> bool:
            cnt = 1
            pre = price[0]
            for i in range(1, n):
                if price[i] - pre >= d:
                    cnt += 1
                    pre = price[i]
            return cnt >= k

        left, right = 0, price[-1] - price[0]
        while left <= right:
            mid = (left + right) // 2
            if check(mid):
                left = mid + 1
            else:
                right = mid - 1
        return right

class Solution {
public:
    int maximumTastiness(vector<int>& price, int k) {
        int n = price.size();
        sort(price.begin(), price.end());

        auto check = [&](int d) {
            int cnt = 1;
            int pre = price[0];
            for (int i = 1; i < n; ++i) {
                if (price[i] - pre >= d) {
                    cnt++;
                    pre = price[i];
                }
            }
            return cnt >= k;
        };

        int left = 0, right = price[n - 1] - price[0];
        while (left <= right) {
            int mid = (left + right) / 2;
            if (check(mid)) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return right;
    }
};