题目难度: 困难
今天继续更新程序员面试金典系列, 大家在公众号 算法精选 里回复 面试金典 就能看到该系列当前连载的所有文章了, 记得关注哦~
题目描述
堆箱子。给你一堆 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 个。
题目思考
- 需要进行哪些预处理?
- 如何得到某个箱子作为顶部的最大高度?
解决方案
思路
- 分析题目, 我们如果可以得到各个箱子作为顶部的最大高度, 那么最终结果自然就是这些高度的最大值了, 那如何得到某个箱子作为顶部的最大高度呢?
- 假设现在有个箱子 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 数组
代码
class Solution:
def pileBox(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 = [h for _, _, h in box]
for j in range(n):
wj, dj, hj = box[j]
for i in range(j):
# 遍历之前的箱子, 只有这部分箱子可能满足长宽高都大于箱子j
wi, di, hi = box[i]
if wi > wj and di > dj and hi > hj:
# 如果箱子i上面可以放箱子j, 那就将dp[j]更新为当前高度和箱子i上面放箱子j的高度的最大值
dp[j] = max(dp[j], dp[i] + hj)
return max(dp) 大家可以在下面这些地方找到我~😊
我的公众号: 算法精选, 欢迎大家扫码关注~😊
京公网安备 11010502036488号