LeetCode 面试题 08.13. 堆箱子
目录
题目描述
题意分析
给一堆箱子，每个箱子用
[宽, 深, 高]三个数描述。可以把箱子叠成一摞，但只有当上面那个箱子的宽、深、高三个维度都严格小于下面那个箱子时才允许叠放。箱子不可旋转。求能叠出的最大总高度。要什么：一个高度数值，不需要给出具体叠了哪些箱子。所以只需要维护最优值，不必回溯方案。
「三个维度都严格小于」这句话定义了一个严格偏序关系。它有两个直接后果。其一，这个关系是传递的——若 A 能叠在 B 上、B 能叠在 C 上，那么 A 的三维都小于 C，A 也能叠在 C 上。传递性保证了「一摞箱子合法」等价于「相邻两两合法」，我们不需要检查非相邻的箱子对。其二，「严格」意味着任何一维相等都不能叠，所以相同尺寸的箱子最多只能用一个。
把它抽象一下：每个箱子是一个节点，若 A 能叠在 B 上就连一条 B → A 的边，那么合法的一摞箱子就是这张有向无环图上的一条链，目标是最大化链上节点的高度之和。这正是带权最长递增子序列（LIS）的结构——只不过「递增」的判据从一维变成了三维同时严格递增，「长度」从计数变成了高度求和。识别出「这是三维 LIS」，整道题就落地了。
约束透露的信号：箱子数量最多 3000，各维尺寸不超过 3000。$n = 3000$ 意味着 $O(n^2) = 9 \times 10^6$ 完全可以接受，而 $O(2^n)$ 的枚举子集绝无可能。也就是说，本题不需要像一维 LIS 那样追求 $O(n \log n)$——事实上三维偏序下的贪心加二分并不成立，$O(n^2)$ 的逐对转移就是标准解。
边界：箱子数组可能为空，返回 0；只有一个箱子时答案就是它的高度；可能存在完全相同的两个箱子，它们互相不能叠；也可能所有箱子都无法互相叠放，此时答案是单个箱子的最大高度，而不是 0。
解法：排序后动态规划求最大堆高
核心思路
先看暴力：枚举箱子的所有子集与所有排列，检查是否构成合法的一摞，取高度和最大者。子集就有 $2^n$ 个，$n = 3000$ 时完全不可行。瓶颈在于：它把「选哪些箱子」和「按什么顺序叠」当成两件独立的事在穷举，而实际上一旦选定了箱子集合，合法的叠放顺序（如果存在）是唯一确定的——必须按尺寸从大到小。
顺着这条线索，先把顺序这一维消掉：对所有箱子按宽度升序排序，宽度相同时按深度升序、再按高度升序。排序之后有一条关键性质：
若箱子
j能叠在箱子i上（j的三维都严格小于i），那么在排序后的数组里必然有j < i。证明只需一行：三维严格小于蕴含
box[j][0] < box[i][0]，而排序的首要关键字正是第 0 维，所以j排在i前面。这条性质把「向所有箱子找可叠对象」收窄成「只向左侧下标找」，转移方向单向化，DP 才有了合法的计算顺序。注意排序只是必要条件而非充分条件：
j < i只说明box[j][0] <= box[i][0]，既可能相等、也没约束另外两维。所以循环体内仍然必须完整地检查三个维度都严格小于——排序负责的是「保证不漏、且转移无环」，判定仍要老老实实做。这一点是本题最容易被误解的地方。于是给出状态定义：
$dp[i]$ 表示以第
i个箱子作为最底层时，能叠出的最大总高度。转移方程是：
\[dp[i] = box[i][2] + \max\left(0,\ \max_{\substack{j < i \\ box[j] \prec box[i]}} dp[j]\right)\]其中 $\prec$ 表示三维都严格小于。初值 $dp[i] = box[i][2]$，代表「只放它自己」这种方案——这个初值同时承担了两个职责：一是处理「没有任何箱子能叠在它上面」的情形，二是保证答案至少是某个箱子的高度而不是 0。
最终答案是 $\max_i dp[i]$，而不是 $dp[n-1]$。因为最优的那一摞未必以尺寸最大的箱子打底——一个很大但很矮的箱子可能还不如一摞中等尺寸的高箱子。这是 LIS 类问题的通病，「以 i 结尾」的状态定义必须配「对所有 i 取最大值」的收尾。
计算顺序上，外层
i从小到大推进，内层枚举j < i。当计算 $dp[i]$ 时，所有 $dp[j]\ (j < i)$ 都已经是最终值，无后效性成立。
解题步骤
- 空数组直接返回 0。为什么：后续要访问
box[0]，空输入会越界；同时「没有箱子」的最大高度确实是 0。- 按第 0 维升序排序，相等时按第 1 维、再按第 2 维升序。为什么必须以第 0 维为首要关键字：它保证了「可叠关系」只会从小下标指向大下标，DP 的计算顺序才有依据。为什么次要关键字也要排：严格来说只排第 0 维就足以保证正确性，但把三维都排上能让相同宽度的箱子按另两维有序排列，便于调试时肉眼核对，成本也只是比较器多两行。
dp[i]初始化为box[i][2]。为什么不是 0：0 表示「一个箱子都不放」，而 $dp[i]$ 的定义是「以i打底」，i本身必然被放上，所以基线是它自己的高度。初值写 0 会让所有答案少算一个箱子的高度。- 内层
j从 0 枚举到i - 1，检查三个维度是否都严格小于。为什么三个都要查：排序只保证了第 0 维不减，第 1、2 维完全没有约束；只查一维会把不合法的叠放算进来。为什么必须是严格小于：题面规定相等不可叠，用<=会让两个同尺寸的箱子叠在一起。- 命中时
dp[i] = max(dp[i], dp[j] + box[i][2])。为什么加的是box[i][2]而不是box[j][2]：$dp[j]$ 已经包含了以j打底的整摞高度，现在把这一整摞放到i上面，新增的正是i自身的高度。- 每轮结束后
answer = max(answer, dp[i])。为什么不能只看dp[n-1]：最优解未必以排序后最后一个箱子打底；必须对全部 $i$ 取最大值。- 返回
answer。answer初值取 0，在n >= 1时第一轮就会被dp[0]更新掉，兼顾了空输入与非空输入两种情形。以
具体用例 box = [[1,1,1], [2,3,4], [2,6,7], [3,4,5]]走一遍，预期答案是 10。排序：按第 0 维升序、第 1 维升序，得到
[[1,1,1], [2,3,4], [2,6,7], [3,4,5]]——本例已经有序，四个箱子记作 A、B、C、D。
i = 0（A =[1,1,1]）：dp[0]初始化为高度 1。内层无j可枚举。answer = max(0, 1) = 1。
i = 1（B =[2,3,4]）：dp[1]初始化为高度 4。
j = 0（A）：检查1 < 2、1 < 3、1 < 4，三维全部严格小于，A 可以叠在 B 上。dp[1] = max(4, dp[0] + 4) = max(4, 1 + 4) = 5。
answer = max(1, 5) = 5。含义是「B 打底、A 在上」这摞高 5。
i = 2（C =[2,6,7]）：dp[2]初始化为高度 7。
j = 0（A）：1 < 2、1 < 6、1 < 7，全部成立。dp[2] = max(7, 1 + 7) = 8。
j = 1（B =[2,3,4]）：第 0 维2 < 2不成立，B 不能叠在 C 上。这正是「排序不能代替判定」的实例——B 的下标小于 C，但它们宽度相同，不满足严格小于。跳过。
answer = max(5, 8) = 8。
i = 3（D =[3,4,5]）：dp[3]初始化为高度 5。
j = 0（A）：1 < 3、1 < 4、1 < 5，成立。dp[3] = max(5, 1 + 5) = 6。
j = 1（B =[2,3,4]）：2 < 3、3 < 4、4 < 5，全部成立。dp[3] = max(6, dp[1] + 5) = max(6, 5 + 5) = 10。这一步把「B 打底、A 在上」的那摞整体搬到了 D 上面，形成 D-B-A 三层。
j = 2（C =[2,6,7]）：第 1 维6 < 4不成立，C 不能叠在 D 上（C 比 D 更深也更高）。跳过。
answer = max(8, 10) = 10。遍历结束，返回 10。核对：D
[3,4,5]在最下、B[2,3,4]居中、A[1,1,1]在顶，三维逐层严格递减，总高5 + 4 + 1 = 10。注意最优解
dp[3] = 10恰好落在最后一个箱子上，但这只是巧合——若把 D 的高度改成 1，则dp[3]变成5 + 1 = 6，而answer仍应取dp[2] = 8。这就是为什么必须对所有 $i$ 取最大值而不能直接返回 $dp[n-1]$。
代码实现
class Solution {
// 题目只要找到一条从某个箱子向更大箱子延展的链，并让链上高度和最大。
public int pileBox(int[][] box) {
if (box == null || box.length == 0) {
return 0;
}
Arrays.sort(
box,
(a, b) -> {
if (a[0] != b[0]) {
return Integer.compare(a[0], b[0]);
}
if (a[1] != b[1]) {
return Integer.compare(a[1], b[1]);
}
return Integer.compare(a[2], b[2]);
}
);
int n = box.length;
int[] dp = new int[n];
int answer = 0;
for (int i = 0; i < n; i++) {
dp[i] = box[i][2];
for (int j = 0; j < i; j++) {
if (box[j][0] < box[i][0]
&& box[j][1] < box[i][1]
&& box[j][2] < box[i][2]) {
dp[i] = Math.max(dp[i], dp[j] + box[i][2]);
}
}
answer = Math.max(answer, dp[i]);
}
return answer;
}
}
func pileBox(box [][]int) int {
// 题目只要找到一条从某个箱子向更大箱子延展的链，并让链上高度和最大。
if len(box) == 0 {
return 0
}
sort.Slice(box, func(i, j int) bool {
if box[i][0] != box[j][0] {
return box[i][0] < box[j][0]
}
if box[i][1] != box[j][1] {
return box[i][1] < box[j][1]
}
return box[i][2] < box[j][2]
})
n := len(box)
dp := make([]int, n)
answer := 0
for i := 0; i < n; i++ {
dp[i] = box[i][2]
for j := 0; j < i; j++ {
if box[j][0] < box[i][0] && box[j][1] < box[i][1] && box[j][2] < box[i][2] {
candidate := dp[j] + box[i][2]
if candidate > dp[i] {
dp[i] = candidate
}
}
}
if dp[i] > answer {
answer = dp[i]
}
}
return answer
}
复杂度分析
- 时间复杂度：$O(n^2)$。凭什么：排序是 $O(n \log n)$，被后面的双层循环吞没；双层循环恰好枚举全部 $n(n-1)/2$ 个下标对，每对做三次比较、一次加法、一次取最大，都是常数。$n = 3000$ 时约 $4.5 \times 10^6$ 次，远在时限之内。这里不能像一维 LIS 那样用贪心加二分优化到 $O(n \log n)$——二分依赖「候选状态可以按单一关键字排成全序」，而三维偏序下两个箱子可能互不可叠（既非小于也非大于），全序不存在。
- 空间复杂度：$O(n)$。凭什么：只额外开了一个长度 $n$ 的
dp数组；排序在 Java 中对对象数组使用 TimSort 需要 $O(n)$ 辅助空间，量级相同。若还需要输出具体叠了哪些箱子，则要再开一个前驱数组记录每次转移的来源，空间仍是 $O(n)$。
关键点总结
- 「多维都严格递增才能接续」= 带权 LIS。看到「必须各维都更小/更大才能衔接」并求某种最优链，先把它归入 LIS 家族，再确定权重是计数（长度）还是求和（高度、价值）。本题的权重是箱子高度，所以转移里加的是
box[i][2]而非 1。- 排序的作用是「消掉一个维度并确立转移方向」，而不是「代替判定」。按第一维排序之后，可叠关系必然从小下标指向大下标，DP 有了合法的计算顺序；但另外两维仍需在循环里逐一检查。混淆这两件事是本题的头号错误。
- 严格偏序的传递性保证了「相邻合法 ⟹ 整摞合法」，这是可以只做逐对转移、不必回头验证整摞的理论依据。若关系不传递（比如「相差不超过 3 才能叠」），这套 DP 立刻失效。
- 「以 i 结尾」的状态必须配「对所有 i 取 max」的收尾。$dp[n-1]$ 不是答案，因为最优链未必在排序后的最后一个元素处终止。这条对 300、354、1048 等全部 LIS 变体一律适用。
- 初值要表达「只有自己」这个最小可行方案。$dp[i] = box[i][2]$ 而非 0，既处理了孤立箱子，也保证了「所有箱子互不可叠」时答案是最高的单个箱子而不是 0。
- 三维偏序无法用贪心加二分优化。一维 LIS 能做到 $O(n \log n)$ 是因为候选可以按值排成全序；三维下存在互不可比的元素对，$O(n^2)$ 已是本题的合理上限。能主动说清这一点，比盲目套二分模板更有说服力。
- 面试视角：这题面试官最想听到的是「这是三维 LIS」这句归类，以及「排序解决第一维、DP 处理剩下两维」的分工。常见追问有三个：一是「箱子能旋转怎么办」——那就把每个箱子的六种（或考虑对称后三种）摆法都展开成独立的箱子再跑同一套 DP；二是「能不能优化到 $O(n \log n)$」——答不能，并说明三维偏序不存在全序；三是「要输出具体方案怎么办」——加一个
from[i]数组记录每次取到最大值时的j，最后从最优的i回溯。能顺带提一句 354. 俄罗斯套娃信封问题 中「第一维相同时第二维要降序排，从而能用二分」的技巧，并解释为什么本题用不上，是很漂亮的对比。
易错点总结
- 错误写法：只依赖排序，内层不再检查第 0 维（写成
if (box[j][1] < box[i][1] && box[j][2] < box[i][2])） → 用例box = [[2,3,4],[2,6,7]]，两个箱子宽度都是 2 不能相叠，但该写法在i = 1时判定3 < 6 && 4 < 7成立，算出dp[1] = 4 + 7 = 11；正确答案是 7。排序只保证第 0 维不减，相等的情形必须被判定挡住。- 错误写法：比较用
<=而不是<→ 用例box = [[1,1,1],[1,1,1]]，两个完全相同的箱子被判定为可叠，返回 2；题面要求三维严格小于，正确答案是 1。- 错误写法：
dp[i]初始化为 0 → 用例box = [[1,1,1]]，dp[0]停在 0，返回 0；正确答案是 1。以i打底意味着i本身一定被放上，基线必须是它自己的高度。- 错误写法：最后返回
dp[n - 1]→ 用例box = [[1,1,100],[1,2,1]]，排序后顺序不变，dp[0] = 100；i = 1时第 0 维1 < 1不成立，两箱不可叠，dp[1] = 1。返回dp[n-1] = 1，而正确答案是 100。最优的一摞未必以排序后的最后一个箱子打底，必须对所有i取最大值。- 错误写法：转移写成
dp[i] = max(dp[i], dp[j] + box[j][2])→ 用例box = [[1,1,1],[2,2,5]]，dp[1]被算成dp[0] + box[0][2] = 1 + 1 = 2，而正确值是dp[0] + box[1][2] = 1 + 5 = 6。$dp[j]$ 已经包含了j及其上方所有箱子的高度，新增的只有i自己。- 错误写法：不排序直接跑双层循环 → 用例
box = [[2,2,2],[1,1,1]]，i = 1时枚举j = 0，检查2 < 1不成立；而真正的可叠关系是box[1]叠在box[0]上，方向是从大下标指向小下标，被单向的内层循环完全错过，返回 2 而不是 3。- 错误写法：排序时把第 0 维降序排 → 用例
box = [[1,1,1],[2,2,2]]，排序后变成[[2,2,2],[1,1,1]]，i = 1时检查2 < 1失败，同样漏掉了唯一的可叠关系，返回 2 而不是 3。方向必须与内层「向左找更小者」一致。- 错误写法：套用 354 题的技巧，第 0 维相同时把第 1 维降序排 → 用例
box = [[2,3,4],[2,6,7]]，降序后是[[2,6,7],[2,3,4]]，结果虽然仍因第 0 维判定而正确，但这个技巧在本题毫无意义：354 的降序是为了配合只用二分处理第二维，而本题三维都要显式判定，画蛇添足反而容易让人误以为可以省掉某一维的检查。- 错误写法：试图用贪心加二分把复杂度降到 $O(n \log n)$ → 用例中存在
[1,5,1]与[5,1,1]这类互不可叠的箱子时，它们在任何单一关键字上都无法排成全序，二分维护的「最优尾部」序列失去意义，结果错误。三维偏序下 $O(n^2)$ 是合理上限。- 错误写法：认为所有箱子互不可叠时应返回 0 → 用例
box = [[3,3,3],[3,3,3]]，答案是 3（放一个箱子），不是 0。只有箱子数组本身为空时才返回 0。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 300. 最长递增子序列 | 中等 | 一维版本且权重为 1，因存在全序可用贪心加二分优化到 $O(n \log n)$ |
| 354. 俄罗斯套娃信封问题 | 困难 | 二维偏序，靠「首维升序、次维降序」的排序技巧把问题降成一维 LIS 从而能用二分 |
| 面试题 17.08. 马戏团人塔 | 中等 | 与 354 同构的身高体重版，同样可用排序加二分，是本题的二维简化对照 |
| 1048. 最长字符串链 | 中等 | 衔接判据是「删一个字符可得」，按长度分组后用哈希表转移，无法靠排序单向化 |
| 368. 最大整除子集 | 中等 | 判据是整除关系，同样具备传递性，但需要额外记录前驱以输出具体子集 |
| 673. 最长递增子序列的个数 | 中等 | 除最优值外还要统计方案数，需要并行维护一个计数数组并处理「等长时累加」 |
| 646. 最长数对链 | 中等 | 一维区间衔接，按右端点排序后贪心即可，展示了「何时贪心可以取代 DP」 |
| 1027. 最长等差数列 | 中等 | 状态要带上公差这一维，转移靠哈希表定位，是 LIS 家族里状态设计的另一种方向 |