What is the core greedy strategy in Maximum Units on a Truck?

Always select boxes with the highest units per box first until the truck is full. This guarantees maximal total units.

Can I use dynamic programming instead of greedy for this problem?

Dynamic programming is unnecessary and less efficient; the greedy approach with sorting suffices to maximize units.

How do I handle remaining capacity if the next box type has more boxes than space left?

Take only as many boxes as fit in the remaining truck capacity and stop when full.

Does the order of boxTypes in the input affect the solution?

No, sorting by units per box ensures the greedy selection works regardless of initial order.

What pattern does this problem illustrate for interviews?

It demonstrates 'Greedy choice plus invariant validation', highlighting decision-making that always maximizes immediate gain while maintaining constraints.

#1710

Easy

auto_awesome贪心·invariant

LeetCode 题解工作台

卡车上的最大单元数

请你将一些箱子装在一辆卡车上。给你一个二维数组 boxTypes ，其中 boxTypes[i] = [numberOfBoxes i , numberOfUnitsPerBox i ] ： numberOfBoxes i 是类型 i 的箱子的数量。 numberOfUnitsPerBox i …

数组贪心排序

题目描述

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

numberOfBoxes_i 是类型 i 的箱子的数量。
numberOfUnitsPerBox_i是类型 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 <= numberOfBoxes_i, numberOfUnitsPerBox_i <= 1000
1 <= truckSize <= 10⁶

lightbulb

解题思路

方法一：贪心 + 排序

根据题意，我们应该选择尽可能多的单元数，因此，我们先对 boxTypes 按照单元数从大到小的顺序排列。

然后从前往后遍历 boxTypes，选择最多 truckSize 个箱子，累加单元数。

时间复杂度 $O(n \times \log n)$ ，其中 $n$ 表示二维数组 boxTypes 的长度。

1

2

3

4

5

6

7

8

9

10

class Solution:
    def maximumUnits(self, boxTypes: List[List[int]], truckSize: int) -> int:
        ans = 0
        for a, b in sorted(boxTypes, key=lambda x: -x[1]):
            ans += b * min(truckSize, a)
            truckSize -= a
            if truckSize <= 0:
                break
        return ans

speed

复杂度分析

指标	值
时间	complexity is O(n log n) due to sorting, where n is the number of box types. Space complexity is O(1) extra space if sorting in place, otherwise O(n). Iteration over box types is linear, O(n).
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Mentions prioritizing boxes with higher units per box.
question_mark
Asks how to handle remaining truck capacity after partial selection of a box type.
question_mark
Looks for proof that greedy selection guarantees maximum units.

warning

常见陷阱

外企场景

error
Failing to sort by units per box, leading to suboptimal total units.
error
Ignoring the truckSize limit when adding boxes, which breaks constraints.
error
Adding boxes of a lower-unit type before exhausting higher-unit types.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Maximize total units with multiple trucks each with different capacities.
arrow_right_alt
Boxes have weights and units; maximize units without exceeding truck weight limit.
arrow_right_alt
Box types may have expiration or priority constraints affecting loading order.

help

常见问题

外企场景

继续练习

#1727 重新排列后的最大子矩阵 #1686 石子游戏 VI #1665 完成所有任务的最少初始能量