程序员面试金典 - 面试题 08.13. 堆箱子

题目难度: 困难

原题链接^[1]

今天继续更新程序员面试金典系列, 大家在gongzhong号 算法精选 里回复 面试金典 就能看到该系列当前连载的所有文章了, 记得哦~

题目描述

堆箱子。给你一堆 n 个箱子，箱子宽 wi、深 di、高 hi。箱子不能翻转，将箱子堆起来时，下面箱子的宽度、高度和深度必须大于上面的箱子。实现一种方法，搭出最高的一堆箱子。箱堆的高度为每个箱子高度的总和。

输入使用数组[wi, di, hi]表示每个箱子。

示例 1:

• 输入：box = [[1, 1, 1], [2, 2, 2], [3, 3, 3]]
• 输出：6

示例 2:

• 输入：box = [[1, 1, 1], [2, 3, 4], [2, 6, 7], [3, 4, 5]]
• 输出：10

提示:

• 箱子的数目不大于 3000 个。

题目思考

1. 需要进行哪些预处理?
2. 如何得到某个箱子作为顶部的最大高度?

解决方案

思路

• 分析题目, 我们如果可以得到各个箱子作为顶部的最大高度, 那么最终结果自然就是这些高度的最大值了, 那如何得到某个箱子作为顶部的最大高度呢?
• 假设现在有个箱子 j, 要想得到它作为顶部的最大高度, 只需要遍历比它更大的箱子, 得到其中最大的高度, 并累加箱子 j 自身的高度, 即可得到箱子 j 作为顶部的最大高度
• 这就是动态规划的典型思路: 假设 dp[j]表示箱子 j 在顶部的最大高度, 那么 dp[j] = max(dp[i]+hj) (箱子 i 的长宽高都要大于箱子 j)
• 而上述做法的前提是: 计算 dp[j] 时, 所有更大箱子的 dp 值都已经计算得到
• 要想满足这一条件, 我们只需要对原数组进行逆序排序, 这样就能保证对于下标为 j 的箱子, 比它更大的箱子的下标只可能小于 j, 而不会大于 j, 这样我们只需要遍历所有小于下标 j 的箱子的 dp 值即可
• 下面的代码就对应了上面的整个过程, 并且有详细的注释, 方便大家理解

复杂度

• 时间复杂度 O(N^2): 两重循环, 每一重循环最多遍历 N 个元素
• 空间复杂度 O(N): 额外 N 个元素的 DP 数组

代码

classSolution:
defpileBox(self,box:List[List[int]])->int:
#先排序再DP
#dp[j]表示箱子j在顶部的最大高度,那么dp[j]=max(dp[i]+hj)(箱子i的长宽高都要大于箱子j)
n=len(box)
#首先对箱子逆序排序,这样下标为0的箱子宽度最大,依次递减,保证了上面的转移方程中的i只可能小于j
box.sort(reverse=True)
#初始化dp值为各个箱子的高度,因为每个箱子至少能达到自身高度
dp=[hfor_,_,hinbox]
forjinrange(n):
wj,dj,hj=box[j]
foriinrange(j):
#遍历之前的箱子,只有这部分箱子可能满足长宽高都大于箱子j
wi,di,hi=box[i]
ifwi>wjanddi>djandhi>hj:
#如果箱子i上面可以放箱子j,那就将dp[j]更新为当前高度和箱子i上面放箱子j的高度的最大值
dp[j]=max(dp[j],dp[i]+hj)
returnmax(dp)

参考资料