卡车上的最大单元数
难度:
标签:
题目描述
代码结果
运行时间: 32 ms, 内存: 16.4 MB
/*
* 思路:
* 1. 将箱子按每个箱子的单元数量从大到小排序。
* 2. 使用Java Stream API来处理数据。
* 3. 通过减少truckSize并累加最大单元数量来得到结果。
*/
import java.util.Arrays;
public class Solution {
public int maximumUnits(int[][] boxTypes, int truckSize) {
return Arrays.stream(boxTypes)
// 按每个箱子的单元数量从大到小排序
.sorted((a, b) -> Integer.compare(b[1], a[1]))
// 累加最大单元数量
.reduce(0, (maxUnits, box) -> {
int numberOfBoxes = box[0];
int numberOfUnitsPerBox = box[1];
int boxesToTake = Math.min(numberOfBoxes, truckSize);
truckSize -= boxesToTake;
return maxUnits + (boxesToTake * numberOfUnitsPerBox);
}, Integer::sum);
}
}
解释
方法:
此题解采用了贪心算法的思想,首先根据每个箱子能装载的单元数量对箱子进行降序排序。排序后,从单元数最多的箱子开始装载,以此确保每次装载能获得最大的单元数。在装载的过程中,根据当前卡车剩余的容量和每种类型箱子的数量来决定实际能装载的箱子数量,直到卡车装满或者所有箱子类型都尝试过为止。
时间复杂度:
O(n log n)
空间复杂度:
O(n)
代码细节讲解
🦆
为什么要选择按照每个箱子的单元数进行降序排序?这种排序方式是否总是能保证得到最大总单元数?
▷🦆
在实现中,如果所有箱子的数量总和小于卡车的容量,算法的输出是否仍然正确,即是否能正确处理卡车未装满的情况?
▷🦆
算法在处理排序后的箱子类型时,如何确定每种箱子的装载数量是否最优化?
▷🦆
在代码中使用了`lambda x: -x[1]`进行排序,这里的`-x[1]`是如何确保按照单元数降序排列的?
▷