LC 1691. 堆叠长方体的最大高度

题目描述

这是 LeetCode 上的 1691. 堆叠长方体的最大高度 ,难度为 困难

给你 n 个长方体 cuboids,其中第 i 个长方体的长宽高表示为 $cuboids[i] = [width_i, length_i, height_i]$(下标从 0 开始)。

请你从 cuboids 选出一个「子集」,并将它们堆叠起来。

如果 $width{i} <= width{j}$ 且 $length{i} <= length{j}$ 且 $height{i} <= height{j}$ ,你就可以将长方体 i 堆叠在长方体 j 上。你可以通过旋转把长方体的长宽高重新排列,以将它放在另一个长方体上。

返回 堆叠长方体 cuboids 可以得到的 最大高度 。

示例 1:

1
2
3
4
5
6
7
8
9
输入: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:

1
2
3
4
5
6
7
输入:cuboids = [[38,25,45],[76,35,3]]

输出:76

解释:
无法将任何长方体放在另一个上面。
选择第 1 个长方体然后旋转它,使 35x3 的一面朝下,其高度为 76

示例 3:
1
2
3
4
5
6
7
8
输入: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 <= width{i}, length{i}, height_{i} <= 100$

排序 + 序列 DP

定义 $f[i]$ 为考虑前 $i$ 个箱子,且必须使用到第 $i$ 个箱子的最大高度。

不难发现,$f[i]$ 至少为当前箱子中的最大边长,而所有 $f[i]$ 的最大值即是答案。

由于题目规定了只有三边都不超过盒子 j 的盒子 i 才能放置在上面,因此我们可以先对三边总和进行「降序」排序。

这样当我们处理到盒子 i 时,所有能够位于盒子 i 底部的盒子 j 均位于 i 左侧,我们可以通过枚举 $j \in [0, i - 1]$ 的盒子,用满足条件的盒子 j 来更新 $f[i]$,即有 $f[i] = \max(f[j] + height_i)$。

实现上,当我们在判定某个盒子 j 是否能够位于盒子 i 的底部时,并不需要枚举两盒子的旋转情况,可以在进行 DP 之前先对所有盒子进行排序预处理(按照升序排序)。

Java 代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
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++ 代码:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
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 代码:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
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 代码:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
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;
};

  • 时间复杂度:$O(n^2)$
  • 空间复杂度:$O(n)$

最后

这是我们「刷穿 LeetCode」系列文章的第 No.1691 篇,系列开始于 2021/01/01,截止于起始日 LeetCode 上共有 1916 道题目,部分是有锁题,我们将先把所有不带锁的题目刷完。

在这个系列文章里面,除了讲解解题思路以外,还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。

为了方便各位同学能够电脑上进行调试和提交代码,我建立了相关的仓库:https://github.com/SharingSource/LogicStack-LeetCode

在仓库地址里,你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。