文章目录题目标题和出处难度题目描述要求示例数据范围解法思路和算法代码复杂度分析题目标题和出处标题卡车上的最大单元数出处1710. 卡车上的最大单元数难度3 级题目描述要求需要将一些箱子装在一辆卡车上。给定一个二维数组boxTypes \texttt{boxTypes}boxTypes其中boxTypes[i] [numberOfBoxes i , numberOfUnitsPerBox i ] \texttt{boxTypes[i] [numberOfBoxes}_\texttt{i}\texttt{, numberOfUnitsPerBox}_\texttt{i}\texttt{]}boxTypes[i] [numberOfBoxesi​, numberOfUnitsPerBoxi​]numberOfBoxes i \texttt{numberOfBoxes}_\texttt{i}numberOfBoxesi​是类型i \texttt{i}i的箱子的数量。numberOfUnitsPerBox i \texttt{numberOfUnitsPerBox}_\texttt{i}numberOfUnitsPerBoxi​是类型i \texttt{i}i的每个箱子可以装载的单元数量。另外给定整数truckSize \texttt{truckSize}truckSize表示卡车上可以装载箱子的最大数量。只要箱子数量不超过truckSize \texttt{truckSize}truckSize就可以选择任意箱子装到卡车上。返回卡车可以装载单元的最大总数。示例示例 1输入boxTypes [[1,3],[2,2],[3,1]], truckSize 4 \texttt{boxTypes [[1,3],[2,2],[3,1]], truckSize 4}boxTypes [[1,3],[2,2],[3,1]], truckSize 4输出8 \texttt{8}8解释箱子的情况如下1 \texttt{1}1个第一类的箱子箱子含3 \texttt{3}3个单元。2 \texttt{2}2个第二类的箱子每个箱子含2 \texttt{2}2个单元。3 \texttt{3}3个第三类的箱子每个箱子含1 \texttt{1}1个单元。可以选择第一类和第二类的所有箱子以及第三类的一个箱子。单元总数是1 × 3 2 × 2 1 × 1 8 \texttt{1} \times \texttt{3} \texttt{2} \times \texttt{2} \texttt{1} \times \texttt{1} \texttt{8}1×32×21×18。示例 2输入boxTypes [[5,10],[2,5],[4,7],[3,9]], truckSize 10 \texttt{boxTypes [[5,10],[2,5],[4,7],[3,9]], truckSize 10}boxTypes [[5,10],[2,5],[4,7],[3,9]], truckSize 10输出91 \texttt{91}91数据范围1 ≤ boxTypes.length ≤ 1000 \texttt{1} \le \texttt{boxTypes.length} \le \texttt{1000}1≤boxTypes.length≤10001 ≤ numberOfBoxes i , numberOfUnitsPerBox i ≤ 1000 \texttt{1} \le \texttt{numberOfBoxes}_\texttt{i}\texttt{, numberOfUnitsPerBox}_\texttt{i} \le \texttt{1000}1≤numberOfBoxesi​, numberOfUnitsPerBoxi​≤10001 ≤ truckSize ≤ 10 6 \texttt{1} \le \texttt{truckSize} \le \texttt{10}^\texttt{6}1≤truckSize≤106解法思路和算法如果箱子总数不超过truckSize \textit{truckSize}truckSize则可以将所有箱子装到卡车上卡车装载的单元总数为所有箱子的单元数量之和。以下考虑箱子总数超过truckSize \textit{truckSize}truckSize的情况。在确定箱子数量为truckSize \textit{truckSize}truckSize的情况下为了使卡车装载的单元总数最大应选择单元数量最大的箱子理由如下。假设选择单元数量最大的truckSize \textit{truckSize}truckSize个箱子时卡车装载的单元总数是maxUnits \textit{maxUnits}maxUnits。将单元数量最大的truckSize \textit{truckSize}truckSize个箱子中的任意一个箱子替换成单元数量更小的箱子替换之后的单元总数会减小单元总数一定小于maxUnits \textit{maxUnits}maxUnits。根据上述分析可以使用贪心的思想计算卡车装载单元的最大总数。具体做法是首先将数组boxTypes \textit{boxTypes}boxTypes按箱子的单元数量降序排序然后从左到右遍历排序后的数组boxTypes \textit{boxTypes}boxTypes在箱子数不超过truckSize \textit{truckSize}truckSize的情况下遍历最多的箱子计算遍历的箱子的单元数量之和即为卡车装载单元的最大总数。代码classSolution{publicintmaximumUnits(int[][]boxTypes,inttruckSize){Arrays.sort(boxTypes,(a,b)-b[1]-a[1]);intmaxUnits0;intboxes0;intlengthboxTypes.length;for(inti0;ilengthboxestruckSize;i){int[]boxTypeboxTypes[i];intnumMath.min(boxType[0],truckSize-boxes);intunitsboxType[1];boxesnum;maxUnitsunits*num;}returnmaxUnits;}}复杂度分析时间复杂度O ( n log ⁡ n ) O(n \log n)O(nlogn)其中n nn是数组boxTypes \textit{boxTypes}boxTypes的长度。排序需要O ( n log ⁡ n ) O(n \log n)O(nlogn)的时间排序之后遍历数组需要O ( n ) O(n)O(n)的时间因此时间复杂度是O ( n log ⁡ n ) O(n \log n)O(nlogn)。空间复杂度O ( n ) O(n)O(n)其中n nn是数组boxTypes \textit{boxTypes}boxTypes的长度。由于待排序数组的元素是数组因此排序需要O ( n ) O(n)O(n)的空间。