题目：

请你将一些箱子装在 一辆卡车 上。给你一个二维数组 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 <= 106

解题思路：

排序 + 贪心

题目要求卡车上的最大单元数，就是让我们求怎么样让卡车能运输最大数量的货物

boxTypes 为二维数组，其中 boxTypes[i] [0]为箱子的数量，boxTypes[i] [1]为一个箱子所能装的货物数量。

truckSize 为卡车所能容纳箱子的数量

那么我们只要每次装箱时候选择能装箱最大的那个箱子即可。

也就是我们对 boxTypes[i][1] 进行递减排序，遍历然后计算即可。

代码：

Python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
    def maximumUnits(self, boxTypes: List[List[int]], truckSize: int) -> int:
        # 排序 + 贪心
        # 将每个箱子能装载的数量进行 递减排序
        ans = 0
        boxTypes = sorted(boxTypes, key=lambda x: x[1], reverse=True)
        for box in boxTypes:
            # 箱子填不满 或 刚好填满
            if truckSize >= box[0]:
                ans += box[0] * box[1]
                truckSize -= box[0]
            else:
                ans += truckSize * box[1]
                break
        return ans

C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    int maximumUnits(vector<vector<int>>& boxTypes, int truckSize) {
        sort(boxTypes.begin(), boxTypes.end(),
        [](vector<int> &a, vector<int> &b) {
            return a[1] > b[1];
        });
        int ans = 0;
        for (auto box: boxTypes) {
            if (truckSize >= box[0]) {
                ans += box[0] * box[1];
                truckSize -= box[0];
            } else {
                ans += truckSize * box[1];
                break;
            }
        }
        return ans;
    }
};

时间复杂度：O(nlogn)

空间复杂度：O(logn)