本文共 2049 字，大约阅读时间需要 6 分钟。

关注我，学习常用算法与数据结构，一题多解，降维打击。

题目描述

[1709]

• https://leetcode-cn.com/problems/maximum-units-on-a-truck/

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

题目剖析&信息挖掘

此题使用贪心算法，单元个数越大的先装，注意总和是否超出int32。

解题思路

方法一 贪心+排序

分析

在箱子个数一定的情况下，单元数越大的箱子先装，使得最后总单元数最大。

思路

bool Cmp(vector
   
     a, vector
    
      b) {
       }class Solution {
   public:    int maximumUnits(vector
     
      
       >& boxTypes, int truckSize) {
           sort(boxTypes.begin(), boxTypes.end(), Cmp); // 按照单元数从大到小排序        int sum = 0, j=truckSize;        for (int i = 0; i < boxTypes.size() && j>0; ++i) {
               // 尽量装多的箱子进去        }                return sum;    }};
      
     
    
   

注意

• 有可能最后卡车装不下所有的箱子。

知识点

• 排序
• 贪心

复杂度

• 时间复杂度：O(nlog(n))
• 空间复杂度：O(n)

参考

代码实现

bool Cmp(vector
   
     a, vector
    
      b) {
       return a[1]> b[1];}class Solution {
   public:    int maximumUnits(vector
     
      
       >& boxTypes, int truckSize) {
           sort(boxTypes.begin(), boxTypes.end(), Cmp); // 按单元数从大到小排序        int sum = 0, j=truckSize;        for (int i = 0; i < boxTypes.size() && j>0; ++i) {
               if (boxTypes[i][0]<=j) {
    // 如果剩下卡车容量可以装下当前规格的箱子。就全装入                sum += boxTypes[i][0]*boxTypes[i][1];                j-=boxTypes[i][0];            } else {
    // 否则就只装目前卡车容量的个数。                sum += j*boxTypes[i][1];                j=0;            }        }                return sum;    }};
      
     
    
   

---

本人码农，希望通过自己的分享，让大家更容易学懂计算机知识。

转载地址：http://dowrz.baihongyu.com/