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 之前先对所有盒子进行排序预处理（按照升序排序）。

代码：

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;
    }
}

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

最后

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

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

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

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