题目描述

礼盒的最大甜蜜度

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

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

返回礼盒的 最大 甜蜜度。

提示

• 1 <= price.length <= 105
• 1 <= price[i] <= 109
• 2 <= k <= price.length

测试用例

用例1：

• 输入：price = [13,5,1,8,21,2], k = 3
• 输出：8
• 解释：选出价格分别为 [13,5,21] 的三类糖果。礼盒的甜蜜度为 min(|13 - 5|, |13 - 21|, |5 - 21|) = min(8, 8, 16) = 8 。 可以证明能够取得的最大甜蜜度就是 8 。

用例2：

• 输入：price = [1,3,1], k = 2
• 输出：2
• 解释：选出价格分别为 [1,3] 的两类糖果。 礼盒的甜蜜度为 min(|1 - 3|) = min(2) = 2 。 可以证明能够取得的最大甜蜜度就是 2 。

用例3：

输入：price = [7,7,7,7], k = 2 输出：0 解释：从现有的糖果中任选两类糖果，甜蜜度都会是 0 。

思路

参考代码注释

代码实现

/**
 * @param {number[]} price
 * @param {number} k
 * @return {number}
 */

/**
  输入price和k
 */
var __readline = require("readline-sync");
__readline.setDefaultOptions({ prompt: "" });
var readline = __readline.prompt;

console.log("请输入price数组: ");
let price = readline().split(" ").map(Number);

console.log("请输入k: ");
let k = readline();

var maximumTastiness = function (price, k) {
  // 最大最小 —— 要想到二分 —— 二分什么 —— 二分甜蜜值
  // 因为选择的差值跟顺序无关，所以可以排序后贪心

  // 二分查找时，下边界为0，上边界为price的最大值与最小值之差 —— 因为mid 是甜蜜度，不是下标

  // price从小到大排序
  price.sort((a, b) => a - b);

  let left = 0,
    right = price[price.length - 1] - price[0];
  while (left < right) {
    const mid = Math.floor((left + right + 1) / 2);
    if (check(price, k, mid)) {
      // mid对应的甜蜜度有可能满足，所以left要取mid
      left = mid;
    } else {
      // mid对应的甜蜜度不满足了，所以right不取mid了
      right = mid - 1;
    }
  }

  return left;
};

const check = (price, k, sweet) => {
  // 因为第一个值一定要取，比如 3 - 1 > 1, 那4 - 1 一定大于1，所以要定义一个与第一个值相减恒为true的值，
  // let prev = -Number.MAX_VALUE / 2;

  // 记录大于甜蜜度sweet的个数
  let cnt = 0;
  let index = 0;
  for (let p of price) {
    // 大于甜蜜度了，个数 ++，同时，另prev为当前值，开始找下一个大于sweet的区间
    // 如果当前值不大于，则遍历下一个值
    if (index == 0) {
      prev = p;
      cnt++;
      index = -1;
      continue;
    }
    if (p - prev >= sweet) {
      cnt++;
      prev = p;
    }
    // 最后看大于当前sweet的个数是否大于等于k
    // 大于等于 —— true，则证明最大甜蜜度应该比传进来的sweet要大，要去二分的右区间继续找
    // 小于 —— false，则证明最大甜蜜度比传进来的sweet要小，要去二分的左区间继续找
  }
  return cnt >= k;
};

let res = maximumTastiness(price, k);
console.log("最大甜蜜度为： ", res);