解决方案：卡车上的最大载货量

由 Mux 赞助的 DEV 全球展示挑战赛：展示你的项目！

这是 LeetCode 解题讲解系列的一部分（索引）。如果您喜欢这篇解题讲解或觉得它有用， 请点赞 此帖和/或 在 LeetCode 论坛上为我的解题帖投票 。

LeetCode 问题 #1710（简单）：卡车上的最大载货量

描述：

（跳转至：解决方案思路||代码：JavaScript | Python | Java | C++）

你的任务是将一定数量的箱子装上一辆卡车。给定一个二维数组boxTypes，其中boxTypes[i] = [numberOfBoxesi, numberOfUnitsPerBoxi]：

• numberOfBoxes i是类型为 的盒子数量i。
• numberOfUnitsPerBox i是每盒该类型商品的单位数量i。

你还会得到一个整数truckSize，它表示卡车上可以装的最大箱子数量。你可以选择任意数量的箱子装上卡车，只要箱子数量不超过该整数即可truckSize。

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

例如：

例1：
输入：	boxTypes = [[1,3],[2,2],[3,1]], truckSize = 4
输出：	8
解释：	共有： - 1 个第一类盒子，内含 3 个单位。- 2 个第二类盒子，每个盒子内含 2 个单位。- 3 个第三类盒子，每个盒子内含 1 个单位。 您可以取出所有第一类和第二类盒子，以及 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

主意：

（跳转至：问题描述||代码：JavaScript | Python | Java | C++）

对于这个问题，我们只需要优先处理更有价值的盒子。为此，我们应该按每个盒子的单元数（B[i][1] ）降序排列盒子类型数组（B ） 。

然后我们可以遍历B，每一步都尽可能多地添加箱子，直到达到卡车容量 ( T )。我们将添加的箱子数量乘以每个箱子的单位数加到答案 ( ans ) 中，并将T减少相同的箱子数量。

当卡车装满（T == 0）或迭代完成后，我们应该返回 ans。

• 时间复杂度：O(N log N)，其中N是B的长度，用于排序
• 空间复杂度：O(1)

Javascript 代码：

（跳转至：问题描述||解决方案思路）

var maximumUnits = function(B, T) {
    B.sort((a,b) => b[1] - a[1])
    let ans = 0
    for (let i = 0; T && i < B.length; i++) {
        let count = Math.min(B[i][0], T)
        ans += count * B[i][1], T -= count
    }
    return ans
};

Python代码：

（跳转至：问题描述||解决方案思路）

class Solution:
    def maximumUnits(self, B: List[List[int]], T: int) -> int:
        B.sort(key=lambda x: x[1], reverse=True)
        ans = 0
        for b,n in B:
            boxes = min(b, T)
            ans += boxes * n
            T -= boxes
            if T == 0: return ans
        return ans

Java 代码：

（跳转至：问题描述||解决方案思路）

class Solution {
    public int maximumUnits(int[][] B, int T) {
        Arrays.sort(B, (a,b) -> b[1] - a[1]);
        int ans = 0;
        for (int[] b : B) {
            int count = Math.min(b[0], T);
            ans += count * b[1];
            T -= count;
            if (T == 0) return ans;
        }
        return ans;
    }
}

C++代码：

（跳转至：问题描述||解决方案思路）

class Solution {
public:
    int maximumUnits(vector<vector<int>>& B, int T) {
        sort(B.begin(), B.end(), [](auto& a, auto& b) { return b[1] < a[1];});
        int ans = 0;
        for (auto& b : B) {
            int count = min(b[0], T);
            ans += count * b[1], T -= count;
            if (!T) return ans;
        }
        return ans;
    }
};