Easy

题目描述

给你一个数组 boxTypes ，其中 boxTypes[i] = [numberOfBoxesi, numberOfUnitsPerBoxi] ：

  • numberOfBoxesi 是类型 i 的箱子的数量。
  • numberOfUnitsPerBoxi 是类型 i 每个箱子可以装载的单元数量。

整数 truckSize 表示卡车上可以装载箱子的最大数量。只要箱子数量不超过 truckSize ，你就可以选择任意箱子装到卡车上。

返回卡车可以装载 单元 的最大总数。

示例 1：

输入：boxTypes = [[1,3],[2,2],[3,1]], truckSize = 4
输出：8
解释：箱子的情况如下：
- 1 个第一类的箱子，里面含 3 个单元。
- 2 个第二类的箱子，每个里面含 2 个单元。
- 3 个第三类的箱子，每个里面含 1 个单元。
你可以选择第一类和第二类的所有箱子，以及第三类的一个箱子。
单元总数 = (1 * 3) + (2 * 2) + (1 * 1) = 8

示例 2：

输入：boxTypes = [[5,10],[2,5],[4,7],[3,9]], truckSize = 10
输出：91

提示：

  • 1 <= boxTypes.length <= 1000
  • 1 <= numberOfBoxesi, numberOfUnitsPerBoxi <= 1000
  • 1 <= truckSize <= 10^6

解题思路

这是一道典型的贪心算法题目。核心思想是优先选择单位价值最高的箱子。

解题思路：

  1. 贪心策略：为了最大化卡车装载的单元数，我们应该优先选择每个箱子单元数最多的箱子类型。

  2. 排序：将箱子类型按照每个箱子的单元数从大到小排序。这样确保我们总是优先考虑价值最高的箱子。

  3. 贪心选择：按照排序后的顺序，对每种箱子类型：

    • 计算当前还能装下多少个箱子（剩余容量）
    • 取该类型箱子数量和剩余容量的较小值
    • 累计单元数，更新剩余容量

  4. 终止条件：当卡车装满或所有箱子都考虑完毕时结束。

算法正确性：贪心选择是最优的，因为如果我们不优先选择单元数最多的箱子，而是选择单元数较少的箱子，那么在相同的箱子数量限制下，总单元数一定不是最优的。

这种方法时间复杂度主要在排序上，空间复杂度为常数级别（不考虑排序的额外空间）。

代码实现

class Solution {
public:
    int maximumUnits(vector<vector<int>>& boxTypes, int truckSize) {
        // 按照每个箱子的单元数从大到小排序
        sort(boxTypes.begin(), boxTypes.end(), [](const vector<int>& a, const vector<int>& b) {
            return a[1] > b[1];
        });
        
        int totalUnits = 0;
        int remainingSize = truckSize;
        
        for (const auto& boxType : boxTypes) {
            if (remainingSize == 0) break;
            
            int numberOfBoxes = boxType[0];
            int unitsPerBox = boxType[1];
            
            // 取当前类型箱子数量和剩余容量的较小值
            int boxesToTake = min(numberOfBoxes, remainingSize);
            totalUnits += boxesToTake * unitsPerBox;
            remainingSize -= boxesToTake;
        }
        
        return totalUnits;
    }
};

class Solution:
    def maximumUnits(self, boxTypes: List[List[int]], truckSize: int) -> int:
        # 按照每个箱子的单元数从大到小排序
        boxTypes.sort(key=lambda x: x[1], reverse=True)
        
        total_units = 0
        remaining_size = truckSize
        
        for numberOfBoxes, unitsPerBox in boxTypes:
            if remaining_size == 0:
                break
            
            # 取当前类型箱子数量和剩余容量的较小值
            boxes_to_take = min(numberOfBoxes, remaining_size)
            total_units += boxes_to_take * unitsPerBox
            remaining_size -= boxes_to_take
        
        return total_units

public class Solution {
    public int MaximumUnits(int[][] boxTypes, int truckSize) {
        // 按照每个箱子的单元数从大到小排序
        Array.Sort(boxTypes, (a, b) => b[1].CompareTo(a[1]));
        
        int totalUnits = 0;
        int remainingSize = truckSize;
        
        foreach (var boxType in boxTypes) {
            if (remainingSize == 0) break;
            
            int numberOfBoxes = boxType[0];
            int unitsPerBox = boxType[1];
            
            // 取当前类型箱子数量和剩余容量的较小值
            int boxesToTake = Math.Min(numberOfBoxes, remainingSize);
            totalUnits += boxesToTake * unitsPerBox;
            remainingSize -= boxesToTake;
        }
        
        return totalUnits;
    }
}

/**
 * @param {number[][]} boxTypes
 * @param {number} truckSize
 * @return {number}
 */
var maximumUnits = function(boxTypes, truckSize) {
    boxTypes.sort((a, b) => b[1] - a[1]);
    
    let totalUnits = 0;
    let remainingCapacity = truckSize;
    
    for (let [boxes, unitsPerBox] of boxTypes) {
        if (remainingCapacity <= 0) break;
        
        let boxesToTake = Math.min(boxes, remainingCapacity);
        totalUnits += boxesToTake * unitsPerBox;
        remainingCapacity -= boxesToTake;
    }
    
    return totalUnits;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n log n)主要消耗在排序上，其中 n 是箱子类型的数量
空间复杂度O(1)只使用常数级别的额外空间（不考虑排序的额外空间）

相关题目