LeetCode每日一题系列
题目：828. 统计子串中的唯一字符
难度：困难
题目
给你 n 个长方体 cuboids ，其中第 i 个长方体的长宽高表示为 cuboids[i] = [widthi, lengthi, heighti]（下标从 0 开始）。请你从 cuboids 选出一个 子集 ，并将它们堆叠起来。
如果 widthi <= widthj 且 lengthi <= lengthj 且 heighti <= heightj ，你就可以将长方体 i 堆叠在长方体 j 上。你可以通过旋转把长方体的长宽高重新排列，以将它放在另一个长方体上。
返回 堆叠长方体 cuboids 可以得到的 最大高度 。
示例
文章来源：https://www.toymoban.com/news/detail-685776.html
思路
排序加动态规划：文章来源地址https://www.toymoban.com/news/detail-685776.html
- 首先我们将所有长方体的长宽高按照从小到大的顺序排放，形如[3,4,5]的格式，最大的元素为高度，其他俩任意分为长和宽。
- 在将整个长方体数组按照从小到大的顺序排列，这里默认是按照数组的第一个元素排列。
- 这里我们从上往下依次摆放长方体，dp数组定义为dp[i]为将第i块长方体放在当前最下面一块时，整体的高度。dp数组的状态转移方程为：当前第i块长方体的高度h+dp[0:i]整体高度的最大值（在该块长方体的长宽高都小于等于某块长方体时才能加）。
- 最后返回dp数组中元素的最大值即可。
题解
class Solution:
def maxHeight(self, cuboids: List[List[int]]) -> int:
# 两步排序
for i in cuboids:
i.sort()
cuboids.sort()
dp = [0] * len(cuboids)
# 状态转移
for i, (_, l2, h2) in enumerate(cuboids):
# 计算符合条件的dp[:i]的最大值
for j, (_, l1, h1) in enumerate(cuboids[:i]):
if l1 <= l2 and h1 <= h2: # 排序后，w1 <= w2 恒成立
dp[i] = max(dp[i], dp[j]) # cuboids[j] 可以堆在 cuboids[i] 上
# 更新状态
dp[i] += h2
return max(dp)
到了这里，关于LeetCode每日一题——1691. 堆叠长方体的最大高度的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
