难度: Hard
堆箱子。给你一堆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
提示:
运行时间: 417 ms
内存: 16.8 MB
class Solution:
def pileBox(self, box: List[List[int]]) -> int:
res = 0
box.sort()
n = len(box)
h = [0] * n
for i in range(n):
wi, di, hi = box[i]
pref = 0
for j in range(i):
wj, dj, hj = box[j]
if wj < wi and dj < di and hj < hi and h[j] > pref:
pref = h[j]
h[i] = pref + hi
res = max(res, h[i])
return res
此题解采用动态规划的思想。首先对箱子进行排序，便于后续比较。之后，定义一个数组 h，其中 h[i] 表示以第 i 个箱子为顶部箱子时能达到的最大高度。对于每个箱子 i，遍历在其之前的所有箱子 j，检查是否可以把箱子 j 堆放在箱子 i 下面（即满足 wi > wj, di > dj, hi > hj 的条件）。如果可以，则计算如果以箱子 j 为基底时的总高度，更新 h[i]。最终，遍历所有的 h[i]，找到最大值即为答案。
时间复杂度: O(n^2)
空间复杂度: O(n)
class Solution:
def pileBox(self, box: List[List[int]]) -> int:
res = 0 # 最终的最大高度
box.sort() # 对箱子进行排序
n = len(box) # 箱子的数量
h = [0] * n # h[i] 代表以第i个箱子为顶层时的最大高度
for i in range(n):
wi, di, hi = box[i] # 当前箱子的宽度，深度，高度
pref = 0 # 记录当前可堆叠的最大高度
for j in range(i):
wj, dj, hj = box[j] # 前一个箱子的宽度，深度，高度
if wj < wi and dj < di and hj < hi and h[j] > pref:
pref = h[j] # 更新可堆叠的最大高度
h[i] = pref + hi # 更新以当前箱子为顶层时的最大高度
res = max(res, h[i]) # 更新结果最大高度
return res # 返回最大高度
在题解中没有明确指定排序规则可能是因为省略了细节，或者默认按照某种标准的全面排序（例如Python中的元组排序会按照元素顺序依次比较）。排序的规则会显著影响算法的效率和简洁性。如果正确排序（例如先按宽度，然后按深度，最后按高度），可以确保在动态规划过程中，每次只需比较前面的箱子是否可以作为当前箱子的基底，从而简化比较过程并减少不必要的比较。不恰当的排序可能导致算法效率降低，因为需要额外的条件判断来确保堆叠是可行的。
数组 h[i] 的定义并不意味着每个箱子都必须使用。它仅表示如果选择将第 i 个箱子作为顶部箱子时能达到的最大高度。在动态规划的过程中，我们会更新每个箱子作为顶部的最大可能高度，但最终的解可能不包括所有箱子。我们是在所有 h[i] 的值中选择最大的一个作为最终结果，这意味着某些箱子可以被跳过，不用于构成最高的堆叠方式。
是的，条件 wj < wi, dj < di, hj < hi 的使用确实意味着箱体尺寸必须严格递减。这种条件确保了每个箱子都可以稳定地放在下一个更大的箱子上面。然而，这样的严格条件确实限制了某些可能的有效堆叠方式。例如，如果两个箱子在宽度和深度上大小相同，但高度不同，按照当前的条件，这两个箱子不能堆叠，即使实际上可能是可行的。这种情况下，可能需要调整算法，允许一定的灵活性，例如考虑非严格递减的条件，或者增加更多的逻辑来处理特殊情况。