【2022-12-10每日一题】1691. 堆叠长方体的最大高度[Hard]
2022-12-10
3分钟阅读时长
2022-12-10每日一题：1691. 堆叠长方体的最大高度
难度：Hard
标签：数组 、 动态规划 、 排序
给你 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
方法一：动态规划+排序
详细思路过程见官方题解，这里只做个人刷题记录，方便后续查询阅读
func maxHeight(cuboids [][]int) int {
for _, c := range cuboids {
sort.Ints(c)
}
sort.Slice(cuboids, func(i, j int) bool {
a, b := cuboids[i], cuboids[j]
// 注意以下判断的括号位置
// 以下判断等价于 a[0] + a[1] + a[2] < b[0] + b[1] + b[2]
return a[0] < b[0] || a[0] == b[0] && (a[1] < b[1] || a[1] == b[1] && a[2] < b[2])
})
n := len(cuboids)
f, ans := make([]int, n), 0
for i := range f {
for j := 0; j < i; j++ {
// 以i作为底
if cuboids[j][1] <= cuboids[i][1] && cuboids[j][2] <= cuboids[i][2] {
f[i] = max(f[i], f[j])
}
}
f[i] += cuboids[i][2]
ans = max(ans, f[i])
}
return ans
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
复杂度分析
- 时间复杂度：$O(n^2)$
- 空间复杂度：O(n)。
方法二：回溯+记忆化搜索
func maxHeight(cuboids [][]int) int {
for _, c := range cuboids {
sort.Ints(c)
}
sort.Slice(cuboids, func(i, j int) bool {
a, b := cuboids[i], cuboids[j]
// 注意以下判断的括号位置
// 以下判断等价于 a[0] + a[1] + a[2] < b[0] + b[1] + b[2]
return a[0] < b[0] || a[0] == b[0] && (a[1] < b[1] || a[1] == b[1] && a[2] < b[2])
})
n := len(cuboids)
memo := make([]int, n)
for i := range memo {
memo[i] = -1
}
var dfs func(int, int) int
dfs = func(top, index int) int {
if index == n {
return 0
}
if top != -1 && memo[top] != -1 {
return memo[top]
}
height := dfs(top, index+1)
if top == -1 || check(cuboids[top], cuboids[index]) {
height = max(height, cuboids[index][2] + dfs(index, index + 1))
}
if (top != -1) {
memo[top] = height
}
return height
}
return dfs(-1, 0)
}
func check(a, b []int) bool {
return a[0] <= b[0] && a[1] <= b[1] && a[2] <= b[2]
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
复杂度分析
- 时间复杂度：$O(n^2)$
- 空间复杂度：O(n)。