LeetCode 题解工作台
堆叠长方体的最大高度
给你 n 个长方体 cuboids ，其中第 i 个长方体的长宽高表示为 cuboids[i] = [width i , length i , height i ] （ 下标从 0 开始 ）。请你从 cuboids 选出一个 子集 ，并将它们堆叠起来。 如果 width i j 且 length i…
3
题型
6
代码语言
3
相关题
当前训练重点
困难 · 状态·转移·动态规划
答案摘要
根据题目描述，长方体 能够放在长方体 上，当且仅当长方体 的“长、宽、高”分别小于等于长方体 的“长、宽、高”。 本题允许我们旋转长方体，意味着我们可以选择长方体的任意一边作为长方体的“高”。对于任意一种合法的堆叠，如果我们把里面每个长方体都旋转至“长 <= 宽 <= 高”，堆叠仍然是合法的，并且能够保证堆叠的高度最大化。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 状态·转移·动态规划 题型思路
题目描述
给你 n 个长方体 cuboids ，其中第 i 个长方体的长宽高表示为 cuboids[i] = [widthi, lengthi, heighti]（下标从 0 开始）。请你从 cuboids 选出一个 子集 ，并将它们堆叠起来。
如果 widthi <= widthj 且 lengthi <= lengthj 且 heighti <= heightj ，你就可以将长方体 i 堆叠在长方体 j 上。你可以通过旋转把长方体的长宽高重新排列，以将它放在另一个长方体上。
返回 堆叠长方体 cuboids 可以得到的 最大高度 。
示例 1：
输入：cuboids = [[50,45,20],[95,37,53],[45,23,12]] 输出：190 解释： 第 1 个长方体放在底部，53x37 的一面朝下，高度为 95 。 第 0 个长方体放在中间，45x20 的一面朝下，高度为 50 。 第 2 个长方体放在上面，23x12 的一面朝下，高度为 45 。 总高度是 95 + 50 + 45 = 190 。
示例 2：
输入：cuboids = [[38,25,45],[76,35,3]] 输出：76 解释： 无法将任何长方体放在另一个上面。 选择第 1 个长方体然后旋转它，使 35x3 的一面朝下，其高度为 76 。
示例 3：
输入：cuboids = [[7,11,17],[7,17,11],[11,7,17],[11,17,7],[17,7,11],[17,11,7]] 输出：102 解释： 重新排列长方体后，可以看到所有长方体的尺寸都相同。 你可以把 11x7 的一面朝下，这样它们的高度就是 17 。 堆叠长方体的最大高度为 6 * 17 = 102 。
提示：
n == cuboids.length1 <= n <= 1001 <= widthi, lengthi, heighti <= 100
解题思路
方法一：排序 + 动态规划
根据题目描述，长方体 能够放在长方体 上，当且仅当长方体 的“长、宽、高”分别小于等于长方体 的“长、宽、高”。
本题允许我们旋转长方体，意味着我们可以选择长方体的任意一边作为长方体的“高”。对于任意一种合法的堆叠，如果我们把里面每个长方体都旋转至“长 <= 宽 <= 高”，堆叠仍然是合法的，并且能够保证堆叠的高度最大化。
因此，我们可以把所有长方体的边长进行排序，使得每个长方体满足“长 <= 宽 <= 高”。然后将每个长方体升序排列。
接下来，我们可以使用动态规划的方法求解本题。
我们定义 表示以长方体 为最底部长方体时的最大高度。我们可以枚举每个长方体 的上方的长方体 ，其中 。如果 可以放在 的上方，那么我们可以得到状态转移方程：
其中 表示长方体 的高度。
最终的答案即为 的最大值。
时间复杂度 ，空间复杂度 。其中 为长方体的数量。
class Solution:
def maxHeight(self, cuboids: List[List[int]]) -> int:
for c in cuboids:
c.sort()
cuboids.sort()
n = len(cuboids)
f = [0] * n
for i in range(n):
for j in range(i):
if cuboids[j][1] <= cuboids[i][1] and cuboids[j][2] <= cuboids[i][2]:
f[i] = max(f[i], f[j])
f[i] += cuboids[i][2]
return max(f)
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | Depends on the final approach |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Candidate demonstrates understanding of dynamic programming with state transitions.
- question_mark
The candidate effectively applies sorting as a preprocessing step to optimize the solution.
- question_mark
The candidate chooses dynamic programming over brute force and handles cuboid rotations well.
常见陷阱
外企场景- error
Forgetting to consider all rotations of the cuboids before attempting to stack them.
- error
Not sorting the cuboids in the correct order, leading to inefficient solutions.
- error
Attempting a brute force solution without recognizing the need for dynamic programming and state transitions.
进阶变体
外企场景- arrow_right_alt
Allow only certain rotations of cuboids.
- arrow_right_alt
Add constraints where the number of cuboids is much larger.
- arrow_right_alt
Explore optimizing space complexity in dynamic programming solutions.