卡车上的最大单元数【LC1710】

You are assigned to put some amount of boxes onto one truck. You are given a 2D array boxTypes, where boxTypes[i] = [numberOfBoxesi, numberOfUnitsPerBoxi]:

• numberOfBoxesi is the number of boxes of type i.

• numberOfUnitsPerBoxi is the number of units in each box of the type i.

You are also given an integer truckSize, which is the maximum number of boxes that can be put on the truck. You can choose any boxes to put on the truck as long as the number of boxes does not exceed truckSize.

Return the maximum total number of units that can be put on the truck.

请你将一些箱子装在 一辆卡车 上。给你一个二维数组 boxTypes ，其中 boxTypes[i] = [numberOfBoxesi, numberOfUnitsPerBoxi] ：

• numberOfBoxesi 是类型 i 的箱子的数量。

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

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

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

又又又崩了，好点我做完了=）

• 思路：贪心

。局部最优：尽可能装载容量大的箱子，即将箱子按照可以装载的单元数量从大到小装到卡车上

。全局最优：箱子数量一定时，能够装载的单元最大

• 实现

。先将箱子按照容量从大到小排序

。依次遍历排序后的箱子，并使用变量统计已装载的单元数量res和箱子数量count

• 如果count+当前箱子数量 boxTypes[i][0] > 卡车容量trunkSize，那么只装载卡车容量-count个箱子，res += (trunkSize - count) * boxTypes\[i][1] 并退出循环

• 如果count+当前箱子数量boxTypes[i][0] > 卡车容量trunkSize，那么只装载boxTypes[i][0] 个箱子，res += boxTypes\[i][0] * boxTypes\[i][1]

• 代码

class Solution {
    public int maximumUnits(int[][] boxTypes, int truckSize) {
      Arrays.sort(boxTypes,new Comparator<int[]>(){
          public int compare(int[] box1, int[] box2){
              return box2[1] - box1[1];
          }
      });
        int res = 0;
        int count = 0;
        for (int i = 0; i < boxTypes.length; i++){
            if (count + boxTypes[i][0] > truckSize){
                res += (truckSize - count) * boxTypes[i][1];
                break;
            }else{
                res += boxTypes[i][0] * boxTypes[i][1]; 
                count += boxTypes[i][0];
            }
        }
        return res;
    }
}

• 复杂度

。时间复杂度：O ( n l o g n )，排序需要用O ( n l o g n ) 的时间

。空间复杂度：O ( 1 )，排序需要用O ( n l o g n ) 的递归调用栈空间