Medium

题目描述

你有 n 个袋子，编号从 0 到 n - 1。给你两个下标从 0 开始的整数数组 capacity 和 rocks。第 i 个袋子最多可以装 capacity[i] 块石头，目前已经装了 rocks[i] 块石头。另外给你一个整数 additionalRocks，表示你可以放置的额外石头数量。

请你将额外的石头放入一些袋子中，返回放置后装满的袋子的 最大 数量。

示例 1：

输入：capacity = [2,3,4,5], rocks = [1,2,4,4], additionalRocks = 2
输出：3
解释：
在袋子 0 中放置 1 块石头，在袋子 1 中放置 1 块石头。
现在每个袋子中的石头数量为 [2,3,4,4]。
袋子 0、1 和 2 装满了，有 3 个袋子装满。
可以证明无法装满超过 3 个袋子。
注意，可能还有其他放置石头的方法也能得到 3 这个答案。

示例 2：

输入：capacity = [10,2,2], rocks = [2,2,0], additionalRocks = 100
输出：3
解释：
在袋子 0 中放置 8 块石头，在袋子 2 中放置 2 块石头。
现在每个袋子中的石头数量为 [10,2,2]。
袋子 0、1 和 2 装满了，有 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

解题思路

这是一道典型的贪心算法题。核心思想是优先填满那些需要最少额外石头的袋子。

解题思路：

  1. 计算缺口：对于每个袋子，计算需要的额外石头数量，即 capacity[i] - rocks[i]
  2. 贪心策略：将所有袋子按照缺口大小从小到大排序，优先填满缺口小的袋子
  3. 模拟填充：按顺序尝试填满每个袋子，直到额外石头用完或所有袋子都装满

为什么贪心策略是正确的？ 如果我们有足够的石头来填满缺口较大的袋子，那么我们一定也能用这些石头填满更多的缺口较小的袋子。因此，为了最大化装满的袋子数量，我们应该优先选择那些需要较少额外石头的袋子。

算法步骤：

  1. 计算每个袋子的缺口值
  2. 对缺口值进行升序排序
  3. 贪心地从缺口最小的袋子开始填充
  4. 统计能够装满的袋子数量

时间复杂度主要来自排序操作，空间复杂度取决于存储缺口值的数组。

代码实现

class Solution {
public:
    int maximumBags(vector<int>& capacity, vector<int>& rocks, int additionalRocks) {
        int n = capacity.size();
        vector<int> needed;
        
        // 计算每个袋子需要的额外石头数量
        for (int i = 0; i < n; i++) {
            needed.push_back(capacity[i] - rocks[i]);
        }
        
        // 按需要的石头数量排序（贪心：优先填充需要石头少的袋子）
        sort(needed.begin(), needed.end());
        
        int count = 0;
        for (int i = 0; i < n; i++) {
            if (additionalRocks >= needed[i]) {
                additionalRocks -= needed[i];
                count++;
            } else {
                break;
            }
        }
        
        return count;
    }
};

class Solution:
    def maximumBags(self, capacity: List[int], rocks: List[int], additionalRocks: int) -> int:
        # 计算每个袋子需要的额外石头数量
        needed = [capacity[i] - rocks[i] for i in range(len(capacity))]
        
        # 按需要的石头数量排序（贪心：优先填充需要石头少的袋子）
        needed.sort()
        
        count = 0
        for need in needed:
            if additionalRocks >= need:
                additionalRocks -= need
                count += 1
            else:
                break
                
        return count

public class Solution {
    public int MaximumBags(int[] capacity, int[] rocks, int additionalRocks) {
        int n = capacity.Length;
        int[] needed = new int[n];
        
        // 计算每个袋子需要的额外石头数量
        for (int i = 0; i < n; i++) {
            needed[i] = capacity[i] - rocks[i];
        }
        
        // 按需要的石头数量排序（贪心：优先填充需要石头少的袋子）
        Array.Sort(needed);
        
        int count = 0;
        for (int i = 0; i < n; i++) {
            if (additionalRocks >= needed[i]) {
                additionalRocks -= needed[i];
                count++;
            } else {
                break;
            }
        }
        
        return count;
    }
}

var maximumBags = function(capacity, rocks, additionalRocks) {
    const n = capacity.length;
    
    // 计算每个袋子需要的额外石头数量
    const needed = [];
    for (let i = 0; i < n; i++) {
        needed.push(capacity[i] - rocks[i]);
    }
    
    // 按需要的石头数量排序（贪心：优先填充需要石头少的袋子）
    needed.sort((a, b) => a - b);
    
    let count = 0;
    for (let i = 0; i < n; i++) {
        if (additionalRocks >= needed[i]) {
            additionalRocks -= needed[i];
            count++;
        } else {
            break;
        }
    }
    
    return count;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n log n)主要来自排序操作，其中 n 是袋子的数量
空间复杂度O(n)需要额外数组存储每个袋子的缺口值

相关题目