题目描述
平台：LeetCode
题号：1691
给你 n 个长方体 cuboids，其中第 i 个长方体的长宽高表示为
（下标从 0 开始）。
请你从 cuboids 选出一个「子集」，并将它们堆叠起来。
如果
且
且
，你就可以将长方体 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：
代码语言：javascript复制输入：cuboids = [[38,25,45],[76,35,3]]
输出：76
解释：
无法将任何长方体放在另一个上面。
选择第 1 个长方体然后旋转它，使 35x3 的一面朝下，其高度为 76 。
示例 3：
代码语言：javascript复制输入：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 。
提示：
排序 序列 DP
定义
为考虑前
个箱子，且必须使用到第
个箱子的最大高度。
不难发现，
至少为当前箱子中的最大边长，而所有
的最大值即是答案。
由于题目规定了只有三边都不超过盒子 j 的盒子 i 才能放置在上面，因此我们可以先对三边总和进行「降序」排序。
这样当我们处理到盒子 i 时，所有能够位于盒子 i 底部的盒子 j 均位于 i 左侧，我们可以通过枚举
的盒子，用满足条件的盒子 j 来更新
，即有
。
实现上，当我们在判定某个盒子 j 是否能够位于盒子 i 的底部时，并不需要枚举两盒子的旋转情况，可以在进行 DP 之前先对所有盒子进行排序预处理（按照升序排序）。
Java 代码：
代码语言：javascript复制class Solution {
public int maxHeight(int[][] cs) {
int n = cs.length;
for (int i = 0; i < n; i ) Arrays.sort(cs[i]);
Arrays.sort(cs, (a, b)->(b[0] b[1] b[2])-(a[0] a[1] a[2]));
int ans = 0;
int[] f = new int[n 10];
for (int i = 0; i < n; i ) {
f[i] = cs[i][2];
for (int j = 0; j < i; j ) {
if (cs[j][0] >= cs[i][0] && cs[j][1] >= cs[i][1] && cs[j][2] >= cs[i][2]) {
f[i] = Math.max(f[i], f[j] cs[i][2]);
}
}
ans = Math.max(ans, f[i]);
}
return ans;
}
}
C 代码：
代码语言：javascript复制class Solution {
public:
int maxHeight(vector<vector<int>>& cs) {
int n = cs.size();
for(int i = 0; i < n; i ) sort(cs[i].begin(), cs[i].end());
sort(cs.begin(), cs.end(), [](vector<int>& a, vector<int>& b){
return a[0] a[1] a[2] > b[0] b[1] b[2];
});
vector<int> f(n 10, 0);
int ans = 0;
for(int i = 0; i < n; i ) {
f[i] = cs[i][2];
for(int j = 0; j < i; j ) {
if(cs[j][0] >= cs[i][0] && cs[j][1] >= cs[i][1] && cs[j][2] >= cs[i][2]) {
f[i] = max(f[i], f[j] cs[i][2]);
}
}
ans = max(ans, f[i]);
}
return ans;
}
};
Python 代码：
代码语言：javascript复制class Solution:
def maxHeight(self, cs):
n = len(cs)
for i in range(n):
cs[i].sort()
cs.sort(key=lambda x: -(x[0] x[1] x[2]))
f, ans = [0] * (n 10), 0
for i in range(n):
f[i] = cs[i][2]
for j in range(i):
if cs[j][0] >= cs[i][0] and cs[j][1] >= cs[i][1] and cs[j][2] >= cs[i][2]:
f[i] = max(f[i], f[j] cs[i][2])
ans = max(ans, f[i])
return ans
TypeScript 代码：
代码语言：javascript复制function maxHeight(cs: number[][]): number {
const n = cs.length;
for (let i = 0; i < n; i ) cs[i].sort((a, b) => a-b);
cs.sort((a, b) => (b[0] b[1] b[2]) - (a[0] a[1] a[2]));
const f: number[] = new Array(n 10).fill(0);
let ans = 0;
for (let i = 0; i < n; i ) {
f[i] = cs[i][2];
for (let j = 0; j < i; j ) {
if (cs[j][0] >= cs[i][0] && cs[j][1] >= cs[i][1] && cs[j][2] >= cs[i][2]) {
f[i] = Math.max(f[i], f[j] cs[i][2]);
}
}
ans = Math.max(ans, f[i]);
}
return ans;
};
- 时间复杂度：
- 空间复杂度：
