2023-3-8 刷题情况

礼盒的最大甜蜜度

题目描述

给你一个正整数数组 price ，其中 price[i] 表示第 i 类糖果的价格，另给你一个正整数 k 。

商店组合 k 类 不同 糖果打包成礼盒出售。礼盒的 甜蜜度 是礼盒中任意两种糖果 价格 绝对差的最小值。

返回礼盒的 最大 甜蜜度。

样例

样例输入

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

样例输出

8
2
0

提示

• $1<=price.length<=10^5$
• $1<=price[i]<=10^9$
• $2<=k<=price.length$

思路

答案具有单调性，且n的范围为$10^5$, 只能使用$O(nlogn)$，可直接使用二分

代码实现

class Solution {int[] price;int k;public int maximumTastiness(int[] price, int k) {Arrays.sort(price);this.price = price;this.k = k;int l = 0;int r = price[price.length-1];while(l <= r){int mid = (r + l) / 2;if(!check(mid)) r = mid - 1;else l = mid + 1;}return r;}private boolean check(int x){int ans = 1;int max = price[0];for(int i = 1; i < price.length; i++){if(price[i] >= max + x){max = price[i];ans++;}}return ans >= k;}
}