装满石头的背包的最大数量

说在前面

🎈每天进行一道算法题目练习，今天的题目是“装满石头的背包的最大数量”，走进贪心算法的世界。

问题描述

现有编号从 0 到 n - 1 的 n 个背包。给你两个下标从 0 开始的整数数组 capacity 和 rocks 。第 i 个背包最大可以装 capacity[i] 块石头，当前已经装了 rocks[i] 块石头。另给你一个整数 additionalRocks ，表示你可以放置的额外石头数量，石头可以往 任意 背包中放置。

请你将额外的石头放入一些背包中，并返回放置后装满石头的背包的 最大 数量。
示例 1：

输入：capacity = [2,3,4,5], rocks = [1,2,4,4], additionalRocks = 2
输出：3

解释：

1 块石头放入背包 0 ，1 块石头放入背包 1 。
每个背包中的石头总数是 [2,3,4,4] 。
背包 0 、背包 1 和 背包 2 都装满石头。
总计 3 个背包装满石头，所以返回 3 。
可以证明不存在超过 3 个背包装满石头的情况。
注意，可能存在其他放置石头的方案同样能够得到 3 这个结果。

示例 2：

输入：capacity = [10,2,2], rocks = [2,2,0], additionalRocks = 100
输出：3

解释：

8 块石头放入背包 0 ，2 块石头放入背包 2 。
每个背包中的石头总数是 [10,2,2] 。
背包 0 、背包 1 和背包 2 都装满石头。
总计 3 个背包装满石头，所以返回 3 。
可以证明不存在超过 3 个背包装满石头的情况。
注意，不必用完所有的额外石头。

提示：

n == capacity.length == rocks.length
1 <= n <= 5 * 10^4
1 <= capacity[i] <= 10^9
0 <= rocks[i] <= capacity[i]
1 <= additionalRocks <= 10^9

思路分析

题目的意思是要我们在已经装了部分石头的背包中添加一定数量的石头，最多能够装满多少个背包。\
以示例一为例来看：capacity = [2,3,4,5], rocks = [1,2,4,4], additionalRocks = 2\
capacity = [2,3,4,5]表示有4个背包，背包的容量分别是2，3，4，5；\
rocks = [1,2,4,4]表示4个背包中已经装有的石头数量，即背包1中装有1个石头，背包2中装有2个石头，背包3中装有4个石头，背包4中装有4个石头。也就是说4个背包剩余的容量分别为1，1，0，1；\
additionalRocks = 2表示背包外还有2个待放入背包的石头。

这道题目我们主要要使用贪心的思想来进行解题，也就是说我们应该想一下怎么放入石头可以使得装满的背包最多？
答案其实是很明显的，只要我们优先将石头装入背包容量剩余最少的背包中，那么我们便可以使用最少的石头来装满一个背包，所以我们可以这样做:

• 1、计算背包剩余容量

背包原有容量减去背包已装有石头数量即可得出现在每个背包的剩余容量。

for (let i = 0; i < capacity.length; i++) {
    capacity[i] -= rocks[i];
}

• 2、将背包进行排序

将背包按剩余容量从小到大进行排序。

capacity = capacity.sort((a, b) => {
    return a - b;
});

• 3、依次往最小容量的背包添加石头

优先往剩余容量最小的背包添加石头，石头用完或者背包全部装满时即停止

while (additionalRocks > 0 && res < capacity.length) {
    if (capacity[res] <= additionalRocks) {
      additionalRocks -= capacity[res++];
    } else {
      break;
    }
}

完整代码如下：

AC代码

/**
 * @param {number[]} capacity
 * @param {number[]} rocks
 * @param {number} additionalRocks
 * @return {number}
 */
var maximumBags = function (capacity, rocks, additionalRocks) {
  for (let i = 0; i < capacity.length; i++) {
    capacity[i] -= rocks[i];
  }
  capacity = capacity.sort((a, b) => {
    return a - b;
  });
  let res = 0;
  while (additionalRocks > 0 && res < capacity.length) {
    if (capacity[res] <= additionalRocks) {
      additionalRocks -= capacity[res++];
    } else {
      break;
    }
  }
  return res;
};

说在后面

🎉这里是 JYeontu，现在是一名前端工程师，有空会刷刷算法题，平时喜欢打打羽毛球🏸 ，平时也喜欢写些东西，既为自己记录📋，也希望可以对大家有那么一丢丢的帮助，写的不好望多多谅解🙇，写错的地方望指出，定会认真改进😊，在此谢谢大家的支持，我们下文再见🙌。