leetcode在力扣 App 中打开
题目描述
题目描述
题解
题解
提交记录
提交记录
代码
代码
测试用例
测试用例
测试结果
测试结果
困难
相关标签
premium lock icon相关企业
提示

给你 n 个长方体 cuboids ,其中第 i 个长方体的长宽高表示为 cuboids[i] = [widthi, lengthi, heighti]下标从 0 开始)。请你从 cuboids 选出一个 子集 ,并将它们堆叠起来。

如果 widthi <= widthjlengthi <= lengthjheighti <= 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.length
  • 1 <= n <= 100
  • 1 <= widthi, lengthi, heighti <= 100
通过次数
16,813/25.7K
通过率
65.4%


icon
相关企业

提示 1
Does the dynamic programming sound like the right algorithm after sorting?

提示 2
Let's say box1 can be placed on top of box2. No matter what orientation box2 is in, we can rotate box1 so that it can be placed on top. Why don't we orient everything such that height is the biggest?


评论 (0)
💡 讨论区规则

1. 请不要在评论区发表题解!

2. 评论区可以发表关于对翻译的建议、对题目的疑问及其延伸讨论。

3. 如果你需要整理题解思路,获得反馈从而进阶提升,可以去题解区进行。

暂无评论

贡献者
© 2025 领扣网络(上海)有限公司
0 人在线
行 1,列 1
运行和提交代码需要登录
cuboids =
[[50,45,20],[95,37,53],[45,23,12]]
Source