leetcode
leetcode 1551 ~ 1600
卡车上的最大单元数

卡车上的最大单元数

难度:

标签:

题目描述

代码结果

运行时间: 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]`是如何确保按照单元数降序排列的?
在Python中,使用`sorted`函数时,`lambda x: -x[1]`作为排序关键字(key function)可以将元素按照元组中第二个元素的负值排序。因为对数字取负会将原有的顺序反转,所以这种方式实际上是将第二个元素(即每个箱子的单元数)按从大到小的顺序排列,从而实现降序排序。

相关问题