2023-03-29每日一题

一、题目编号

二、题目链接

点击跳转到题目位置

三、题目描述

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

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

返回礼盒的 最大 甜蜜度。

提示：

• 1 <= price.length <= 10⁵
• 1 <= price[i] <= 10⁹
• 2 <= k <= price.length

四、解题代码

class Solution {bool judge(int degree, vector<int> &price , int k, int n){int num = 1;int index = price[0];for(int i = 1; i < n; ++i){if(price[i] - index >= degree){index = price[i];++num;}}if(num >= k){return true;}return false;}public:int maximumTastiness(vector<int>& price, int k) {sort(price.begin(), price.end());int n = price.size();int left = 0;int right = price[n - 1] - price[0];int ans = -1;while(left <= right){int mid = ((right - left) >> 1) + left;if(judge(mid, price, k, n) == true){ans = mid;left = mid+1;} else{right = mid-1;}}return ans;}
};

五、解题思路

(1) 这道题目采用的是二分答案+贪心的方式来解决本道题目。

(2) 首先将价格从低到高来进行排序，那么最小的甜蜜度肯定为0，最大的甜蜜度肯定为price[n-1] - price[0]。那么我们就可以用二分答案的方式，在这个甜蜜度区间内进行查找，直到查找到答案。

(3) 那么我们怎么判断二分查找的答案是正确的呢。假设我们判断甜蜜度degree的答案是正确，那就是遍历一个有序数组，找到k个满足间隔大于等于degree的数。这个问题显然是熟悉的贪心思路（样板为活动安排问题）。

(4) 最后返回二分搜索出来的答案即可。