堆叠长方体的最大高度
难度:
标签:
题目描述
给你 n 个长方体 cuboids ，其中第 i 个长方体的长宽高表示为 cuboids[i] = [widthi, lengthi, heighti]（下标从 0 开始）。请你从 cuboids 选出一个 子集 ，并将它们堆叠起来。
如果 widthi <= widthj 且 lengthi <= lengthj 且 heighti <= 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.length1 <= n <= 1001 <= widthi, lengthi, heighti <= 100
代码结果
运行时间: 31 ms, 内存: 16.1 MB
/*
* 思路：
* 1. 首先将每个长方体的尺寸进行排序，使得宽度<=长度<=高度。
* 2. 对这些排序后的长方体按它们的长宽高进行排序。
* 3. 使用动态规划来求解：dp[i] 表示以第 i 个长方体为底时的最大堆叠高度。
* 4. 最后从 dp 数组中找出最大值，即为所求。
*/
import java.util.Arrays;
import java.util.Comparator;
public class MaxHeightOfCuboidsStream {
public int maxHeight(int[][] cuboids) {
// Step 1 & 2: 对每个长方体的尺寸进行排序，并按长宽高排序
Arrays.stream(cuboids).forEach(Arrays::sort);
cuboids = Arrays.stream(cuboids)
.sorted((a, b) -> {
if (a[0] != b[0]) return a[0] - b[0];
if (a[1] != b[1]) return a[1] - b[1];
return a[2] - b[2];
})
.toArray(int[][]::new);
int n = cuboids.length;
int[] dp = new int[n];
int maxHeight = 0;
// Step 3: 动态规划求解最大高度
for (int i = 0; i < n; i++) {
dp[i] = cuboids[i][2];
for (int j = 0; j < i; j++) {
if (cuboids[j][0] <= cuboids[i][0] && cuboids[j][1] <= cuboids[i][1] && cuboids[j][2] <= cuboids[i][2]) {
dp[i] = Math.max(dp[i], dp[j] + cuboids[i][2]);
}
}
maxHeight = Math.max(maxHeight, dp[i]);
}
return maxHeight;
}
}
解释
方法:
这个问题可以通过动态规划解决。首先，我们需要处理每个长方体，让它的三个维度按照非降序排序，这样对于每个长方体，我们总是可以确保宽度是最小的，长度是中等的，高度是最大的。接着，我们对整个长方体数组进行排序，这样我们可以基于宽度和长度的非降序来处理它们。在动态规划数组 `f` 中，`f[i]` 表示以第 `i` 个长方体为顶部的最大堆叠高度。对于每个长方体 `i`，我们会遍历在它之前的所有长方体 `j`，检查是否可以将 `j` 堆叠在 `i` 上。这是基于比较长度和高度，因为宽度已经通过排序保证了。如果可以堆叠，我们就更新 `f[i]` 为 `f[j] + height of i` 中的最大值。最后，我们的答案是 `f` 中的最大值，即所有可能的堆叠配置中的最大高度。
时间复杂度:
O(n^2)
空间复杂度:
O(n)
代码细节讲解
🦆
为什么在处理每个长方体之前，需要将它们的尺寸进行非降序排序？
▷🦆
在进行所有长方体排序时，排序的依据是什么？是否仅基于宽度，还是宽度和长度都有考虑？
▷🦆
动态规划数组`f[i]`中的更新逻辑，为什么是`f[i] = max(f[i], f[j] + h2)`？这里的`h2`代表什么？
▷