LeetCode 面试题 08.13. 堆箱子

约 6 分钟
文章信息 8 个分类 3 个标签
分类
LeetCode CodeTop 困难 未解决 2-5 程序员面试金典（第 6 版） 字节 阿里
标签
数组 动态规划 排序

题目描述

✅ 面试题 08.13. 堆箱子

image-20260928230535296

题意分析

每个箱子用 [宽, 深, 高] 表示，不能旋转。上层箱子的宽、深、高都必须严格小于紧挨着它的下层箱子，目标是使整摞箱子的高度之和最大。

不要求使用全部箱子，也不是最大化箱子的个数。高度既是能否叠放的一项尺寸限制，也是计入答案的权重。

解法：排序后动态规划求最大堆高

核心思路

[!blue]

先按宽度升序排列箱子，代码在同宽时再依次按深度、高度排序。这样，凡是能放在箱子 i 上面的箱子，宽度都严格更小，一定已经出现在它前面。排序只是建立计算顺序，不会改变单个箱子的宽、深、高含义，也不能代替叠放条件检查。

定义 dp[i] 为必须以箱子 i 作为最底层时，能得到的最大堆高。只使用当前箱子也是合法方案，所以先令 dp[i] = box[i][2]。

如果箱子 j 的三维都严格小于箱子 i，就可以把“以 j 打底的最优整摞”放到 i 上面，新高度为 dp[j] + box[i][2]。加入 i 只需要检查它与直接相邻的 j 是否匹配，j 上方的箱子已经在 dp[j] 中形成合法堆叠。

任意以 i 打底的堆叠，要么只有 i，要么有一个直接放在它上面的箱子 j。枚举所有合法的 j 并取最大值，就覆盖了全部选择；把 j 上方替换成同底箱的最优方案，只会增加高度，不会破坏叠放关系。

最后对所有 dp[i] 取最大值。排序后的最后一个箱子虽然宽度最大，却未必在深度和高度上适合承托最优堆叠，因此不能只返回最后一个状态。

解题步骤

  1. 空数组返回 0，否则按宽、深、高的字典序对整组箱子排序；原输入中的箱子顺序会被改变。
  2. 从前向后枚举底箱 i，将 dp[i] 初始化为它自身的高度。
  3. 枚举所有 j < i，逐一检查宽、深、高是否都严格小于箱子 i。
  4. 若可以叠放，就用 dp[j] + box[i][2] 更新 dp[i]。
  5. 每个底箱处理完后，用 dp[i] 更新全局最大高度，最终返回这个最大值。

代码实现

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;
    }
}

import "sort"

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
}

复杂度分析

设箱子数量为 n。

  • 时间复杂度：$O(n^2)$。排序为 $O(n\log n)$，随后每对前后箱子最多比较一次，动态规划占主导。
  • 空间复杂度：$O(n)$，来自状态数组和排序辅助空间。

关键点总结

[!green]

  • 按宽度排序让所有合法上层箱子的状态先算出来，但转移仍要检查全部三维。
  • dp[i] 固定的是底箱，保存的是整摞高度，因此接上新底箱只需加它自己的高度。
  • 每个箱子都可能是最优方案的底箱，答案应取所有状态的最大值。

易错点总结

[!yellow]

  • 对每个箱子的三个尺寸单独排序：相当于改变箱子的朝向，而本题不允许旋转。
  • 排序后只检查深度和高度：同宽箱子仍不能叠放，三维都必须严格小于。
  • 把严格小于写成小于等于：任意一维相等都会使这次叠放不合法。
  • 把 dp[j] 与底箱高度比较：尺寸限制比较的是箱子 j 自身的高度，不是它和上方整摞的总高度。
  • 转移时再加箱子 j 的高度：dp[j] 已经包含它，只需额外加上当前底箱 i 的高度。
  • 只返回最后一个状态：宽度最大的箱子未必能构成最高堆叠。

相似题目

题目 难度 关联与区别
354. 俄罗斯套娃信封问题 困难 原题两维严格递增且最大化数量，本题三维都严格增大并最大化高度和。
1691. 堆叠长方体的最大高度 困难 原题允许旋转并采用非严格尺寸兼容，本题禁止旋转且三维必须严格比较，不能照搬单箱维度排序。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2026/24544463
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！