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 原题链接和其他优选题解。