LilyChenlin
0%

leetcode-6006.拿出最少数目的魔法豆

发表于 更新于 分类于 本文字数： 752 阅读时长 ≈ 1 分钟

[来源] 🔗6006.拿出最少数目的魔法豆

题目

给你一个 正 整数数组 beans ，其中每个整数表示一个袋子里装的魔法豆的数目。

请你从每个袋子中 拿出 一些豆子（也可以 不拿出），使得剩下的 非空 袋子中（即 至少 还有 一颗 魔法豆的袋子）魔法豆的数目 相等 。一旦魔法豆从袋子中取出，你不能将它放到任何其他的袋子中。

请你返回你需要拿出魔法豆的 最少数目。

示例 1:

1
2
3
4
5
6
7
8
9
10
11
12
输入：beans = [4,1,6,5]
输出：4
解释：
- 我们从有 1 个魔法豆的袋子中拿出 1 颗魔法豆。
  剩下袋子中魔法豆的数目为：[4,0,6,5]
- 然后我们从有 6 个魔法豆的袋子中拿出 2 个魔法豆。
  剩下袋子中魔法豆的数目为：[4,0,4,5]
- 然后我们从有 5 个魔法豆的袋子中拿出 1 个魔法豆。
  剩下袋子中魔法豆的数目为：[4,0,4,4]
总共拿出了 1 + 2 + 1 = 4 个魔法豆，剩下非空袋子中魔法豆的数目相等。
没有比取出 4 个魔法豆更少的方案。

思路

  1. 拿出魔法豆 + 剩余魔法豆 = 初始魔法豆

  2. 考虑拿出最少数目的魔法豆，可以转化为剩余最多的魔法豆。

  3. beans数组的长度为n，对于每个i袋子，可以剩余的最多魔法豆为

    (n - i) * beans[i]

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
function minimumRemoval(beans: number[]): number {
    let 
        len = beans.length,
        sum = 0,
        maxSum = 0; // 针对每个袋子可以拿出的魔法豆
    beans.sort((a, b) => a - b)
    for (let i = 0; i < beans.length; i++) {
        sum += beans[i];
        maxSum = Math.max(maxSum, beans[i] * (len - i) )
    }

    return sum - maxSum
};