2022-12-10 1691. 堆叠长方体的最大高度 (hard)

🚩 学如逆水行舟,不进则退。 —— 《增广贤文》

题目描述:

给你 n 个长方体 cuboids ,其中第 i 个长方体的长宽高表示为 cuboids[i] = [width(i), length(i), height(i)](下标从 0 开始)。请你从 cuboids 选出一个 子集 ,并将它们堆叠起来。
如果 width(i) <= width(j) 且 length(i) <= length(j) 且 height(i) <= height(j) ,你就可以将长方体 i 堆叠在长方体 j 上。你可以通过旋转把长方体的长宽高重新排列,以将它放在另一个长方体上。
返回 堆叠长方体 cuboids 可以得到的 最大高度 。


测试用例:

leetcode每日一题寒假版:1691. 堆叠长方体的最大高度 (hard)( 换了皮的最长递增子序列)-LMLPHP


分析:

本题允许我们旋转长方体,意味着我们可以选择长方体的任意一边作为长方体的“高”。对于任意一种合法的堆叠,如果我们把里面每个长方体都旋转至“长 <= 宽 <= 高”,堆叠仍然是合法的,并且能够保证堆叠的高度最大化。

因此,我们可以把所有长方体的边长进行排序,使得每个长方体满足“长 <= 宽 <= 高”。然后将每个长方体升序排列。
然后本题就可以转化成经典的线性dp问题最长递增子序列
来源:力扣(LeetCode)ylb:https://leetcode.cn/problems/maximum-height-by-stacking-cuboids/solutions/2014535/by-lcbin-1uv5/


代码:

func maxHeight(cuboids [][]int) (ans int) {
    for _, v := range cuboids {
        sort.Ints(v)   //对每个长方体按照长 <= 宽 <= 高排序
    }
    //将每个长方体升序排列
    sort.Slice(cuboids, func(i, j int) bool {  
        a, b := cuboids[i], cuboids[j]
        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 := make([]int, n)
    for i := range f { //这里dp的意思大致是将第i个长方体堆叠在之前最高长度的堆叠体上,而j就是已经堆叠的长方体
        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]  //加上之前最高堆叠体高度就是第i个最高堆叠体
        ans = max(ans, f[i])   //每次循环求得最大的结果
    }
    return
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}
12-11 16:25