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) 最后返回二分搜索出来的答案即可。