2517. 禮盒的最大甜蜜度（Maximum Tastiness of Candy Box）

問(wèn)題描述

給定一個(gè)正整數(shù)數(shù)組 price，其中 price[i] 表示第 i 類(lèi)糖果的價(jià)格，另給定一個(gè)正整數(shù) k。商店將 k 類(lèi)不同糖果組合成禮盒出售。禮盒的甜蜜度是禮盒中任意兩種糖果價(jià)格絕對(duì)差的最小值。

要求我們返回禮盒的最大甜蜜度。

示例

示例 1：

輸入：

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

輸出：

8

解釋：
選出價(jià)格分別為 [13, 5, 21] 的三類(lèi)糖果。禮盒的甜蜜度為 min(|13 - 5|, |13 - 21|, |5 - 21|) = min(8, 8, 16) = 8。

示例 2：

輸入：

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

輸出：

2

解釋：
選出價(jià)格分別為 [1, 3] 的兩類(lèi)糖果。禮盒的甜蜜度為 min(|1 - 3|) = min(2) = 2。

示例 3：

輸入：

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

輸出：

0

解釋：
從現(xiàn)有的糖果中任選兩類(lèi)糖果，甜蜜度都會(huì)是 0。

解題思路

1. 問(wèn)題分析

我們需要從 price 數(shù)組中選擇 k 類(lèi)糖果，這些糖果的甜蜜度是由它們的價(jià)格差決定的，而我們需要找到一種選擇方法，使得最大甜蜜度盡可能大。

• 甜蜜度的定義：禮盒中任意兩種糖果價(jià)格的絕對(duì)差的最小值。
• 目標(biāo)：最大化禮盒的最小價(jià)格差。

2. 關(guān)鍵觀察

• 排序： 將 price 數(shù)組排序后，糖果的價(jià)格差會(huì)變得更加規(guī)律。因?yàn)槿绻x擇相鄰的價(jià)格差，顯然會(huì)更小。
• 二分查找： 為了找到最大甜蜜度，我們可以用二分查找來(lái)試探不同的甜蜜度，逐漸逼近最優(yōu)解。

3. 解法步驟

• 排序： 首先對(duì) price 數(shù)組進(jìn)行排序，使得選擇的糖果價(jià)格差最小。

• 二分查找： 設(shè)定一個(gè)甜蜜度的范圍，從 0 到 price[-1] - price[0]。在此范圍內(nèi)進(jìn)行二分查找，檢查是否可以選出 k 類(lèi)糖果，使得它們的最小價(jià)格差大于等于當(dāng)前的 mid。

• 貪心選擇： 對(duì)于每一個(gè)候選的甜蜜度 d，我們可以通過(guò)貪心算法來(lái)選擇糖果。遍歷價(jià)格數(shù)組，確保每個(gè)新選擇的糖果價(jià)格與之前選擇的糖果價(jià)格差不小于 d，如果滿(mǎn)足條件，則繼續(xù)選擇糖果。

4. 代碼實(shí)現(xiàn)

from typing import Listclass Solution:def maximumTastiness(self, price: List[int], k: int) -> int:# 輔助函數(shù)：判斷是否可以選出至少 k 個(gè)糖果，且其最小價(jià)格差大于等于 ddef f(d: int) -> int:cnt = 1  # 選擇第一個(gè)糖果pre = price[0]  # 上一個(gè)選擇的糖果的價(jià)格for p in price:if p >= pre + d:  # 當(dāng)前糖果價(jià)格與前一個(gè)糖果價(jià)格差 >= dcnt += 1pre = p  # 更新上一個(gè)選擇的糖果return cntprice.sort()  # 對(duì)價(jià)格數(shù)組進(jìn)行排序left = 0  # 二分查找的左邊界right = (price[-1] - price[0]) // (k - 1) + 1  # 二分查找的右邊界# 二分查找最大甜蜜度while left + 1 < right:mid = (left + right) // 2if f(mid) >= k:  # 如果可以選擇 k 個(gè)糖果，返回 midleft = midelse:right = midreturn left

5. 時(shí)間復(fù)雜度

• 排序操作的時(shí)間復(fù)雜度為 O(n log n)，其中 n 是 price 數(shù)組的長(zhǎng)度。
• 二分查找的時(shí)間復(fù)雜度為 O(log(max_price - min_price))。
• 對(duì)每一個(gè)中間值 mid，我們需要遍歷一次 price 數(shù)組，時(shí)間復(fù)雜度為 O(n)。

因此，總的時(shí)間復(fù)雜度為 O(n log n + n log(max_price - min_price))，其中 n 是糖果數(shù)量，max_price - min_price 是糖果價(jià)格的范圍。

6. 總結(jié)

本題通過(guò)對(duì)糖果價(jià)格數(shù)組排序，并利用二分查找和貪心策略來(lái)最大化糖果禮盒的甜蜜度。這個(gè)解法不僅高效，還能通過(guò)二分查找不斷逼近最優(yōu)解，從而找到最大的甜蜜度。