堆叠长方体的最大高度

1691. 堆叠长方体的最大高度

给你 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 可以得到的 最大高度 。

示例 1：

输入：cuboids = [[50,45,20],[95,37,53],[45,23,12]]
输出：190
解释：
第 1 个长方体放在底部，53x37 的一面朝下，高度为 95 。
第 0 个长方体放在中间，45x20 的一面朝下，高度为 50 。
第 2 个长方体放在上面，23x12 的一面朝下，高度为 45 。
总高度是 95 + 50 + 45 = 190 。

示例 2：

输入：cuboids = [[38,25,45],[76,35,3]]
输出：76
解释：
无法将任何长方体放在另一个上面。
选择第 1 个长方体然后旋转它，使 35x3 的一面朝下，其高度为 76 。

示例 3：

输入：cuboids = [[7,11,17],[7,17,11],[11,7,17],[11,17,7],[17,7,11],[17,11,7]]
输出：102
解释：
重新排列长方体后，可以看到所有长方体的尺寸都相同。
你可以把 11x7 的一面朝下，这样它们的高度就是 17 。
堆叠长方体的最大高度为 6 * 17 = 102 。

提示：

n == cuboids.length
1 <= n <= 100
1 <= width_i, length_i, height_i <= 100

原站题解

去查看

上次编辑到这里，代码来自缓存点击恢复默认模板

class Solution { public: int maxHeight(vector<vector<int>>& cuboids) { } };

python3 解法, 执行用时: 120 ms, 内存消耗: 18.7 MB, 提交时间: 2022-12-10 11:38:13

class Solution:
    def maxHeight(self, cuboids: List[List[int]]) -> int:
        def check(a: List[int], b: List[int]) -> bool:
            return a[0] <= b[0] and a[1] <= b[1] and a[2] <= b[2]

        n = len(cuboids)
        for c in cuboids:
            c.sort()
        cuboids.sort(key=sum)

        @cache
        def dfs(top: int, index: int) -> int:
            if index == n:
                return 0
            height = dfs(top, index + 1)
            if top == -1 or check(cuboids[top], cuboids[index]):
                height = max(height, cuboids[index][2] + dfs(index, index + 1))
            return height
        return dfs(-1, 0)

java 解法, 执行用时: 5 ms, 内存消耗: 41.3 MB, 提交时间: 2022-12-10 11:38:02

class Solution {
    public int maxHeight(int[][] cuboids) {
        int n = cuboids.length;
        for (int[] v : cuboids) {
            Arrays.sort(v);
        }
        Arrays.sort(cuboids, (a, b) -> (a[0] + a[1] + a[2]) - (b[0] + b[1] + b[2]));

        int[] memo = new int[n];
        Arrays.fill(memo, -1);
        return dfs(cuboids, memo, -1, 0);
    }

    public int dfs(int[][] cuboids, int[] memo, int top, int index) {
        if (index == cuboids.length) {
            return 0;
        }
        if (top != -1 && memo[top] != -1) {
            return memo[top];
        }
        int height = dfs(cuboids, memo, top, index + 1);
        if (top == -1 || check(cuboids[top], cuboids[index])) {
            height = Math.max(height, cuboids[index][2] + dfs(cuboids, memo, index, index + 1));
        }
        if (top != -1) {
            memo[top] = height;
        }
        return height;
    }

    public boolean check(int[] a, int[] b) {
        return a[0] <= b[0] && a[1] <= b[1] && a[2] <= b[2];
    }
}

javascript 解法, 执行用时: 80 ms, 内存消耗: 43.2 MB, 提交时间: 2022-12-10 11:37:45

/**
 * @param {number[][]} cuboids
 * @return {number}
 */
var maxHeight = function(cuboids) {
    const n = cuboids.length;
    for (const v of cuboids) {
        v.sort((a, b) => a - b);
    }
    cuboids.sort((a, b) => (a[0] + a[1] + a[2]) - (b[0] + b[1] + b[2]));

    const memo = new Array(n).fill(-1)

    const dfs = (cuboids, memo, top, index) => {
        if (index === cuboids.length) {
            return 0;
        }
        if (top !== -1 && memo[top] !== -1) {
            return memo[top];
        }
        let height = dfs(cuboids, memo, top, index + 1);
        if (top === -1 || check(cuboids[top], cuboids[index])) {
            height = Math.max(height, cuboids[index][2] + dfs(cuboids, memo, index, index + 1));
        }
        if (top != -1) {
            memo[top] = height;
        }
        return height;
        }
    return dfs(cuboids, memo, -1, 0);
}

const check = (a, b) => {
    return a[0] <= b[0] && a[1] <= b[1] && a[2] <= b[2];
};

javascript 解法, 执行用时: 64 ms, 内存消耗: 43.4 MB, 提交时间: 2022-12-10 11:37:24

/**
 * @param {number[][]} cuboids
 * @return {number}
 */
var maxHeight = function(cuboids) {
    const n = cuboids.length;
    for (const v of cuboids) {
        v.sort((a, b) => a - b);
    }
    cuboids.sort((a, b) => (a[0] + a[1] + a[2]) - (b[0] + b[1] + b[2]));
    let ans = 0;
    const dp = new Array(n).fill(0);
    for (let i = 0; i < n; i++) {
        dp[i] = cuboids[i][2];
        for (let j = 0; j < i; j++) {
            if (cuboids[i][0] >= cuboids[j][0] && 
                cuboids[i][1] >= cuboids[j][1] && 
                cuboids[i][2] >= cuboids[j][2]) {
                dp[i] = Math.max(dp[i], dp[j] + cuboids[i][2]);
            }
        }
        ans = Math.max(ans, dp[i]);
    }
    return ans;
};

cpp 解法, 执行用时: 12 ms, 内存消耗: 8.7 MB, 提交时间: 2022-12-10 11:35:24

class Solution {
public:
    int maxHeight(vector<vector<int>> &cuboids) {
        for (auto &c : cuboids)
            sort(c.begin(), c.end());
        sort(cuboids.begin(), cuboids.end());
        int n = cuboids.size(), f[n];
        for (int i = 0; i < n; ++i) {
            f[i] = 0;
            for (int j = 0; j < i; ++j)
                // 排序后，cuboids[j][0] <= cuboids[i][0] 恒成立
                if (cuboids[j][1] <= cuboids[i][1] && cuboids[j][2] <= cuboids[i][2])
                    f[i] = max(f[i], f[j]); // cuboids[j] 可以堆在 cuboids[i] 上
            f[i] += cuboids[i][2];
        }
        return *max_element(f, f + n);
    }
};

golang 解法, 执行用时: 4 ms, 内存消耗: 2.8 MB, 提交时间: 2022-12-10 11:34:54

func maxHeight(cuboids [][]int) (ans int) {
    for _, c := range cuboids {
        sort.Ints(c)
    }
    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])
    })
    f := make([]int, len(cuboids))
    for i, c2 := range cuboids {
        for j, c1 := range cuboids[:i] {
            if c1[1] <= c2[1] && c1[2] <= c2[2] { // 排序后，c1[0] <= c2[0] 恒成立
                f[i] = max(f[i], f[j]) // c1 可以堆在 c2 上
            }
        }
        f[i] += c2[2]
        ans = max(ans, f[i])
    }
    return
}

func max(a, b int) int { if b > a { return b }; return a }

java 解法, 执行用时: 5 ms, 内存消耗: 40.7 MB, 提交时间: 2022-12-10 11:34:30

class Solution {
    public int maxHeight(int[][] cuboids) {
        for (int[] c : cuboids)
            Arrays.sort(c);
        Arrays.sort(cuboids, (a, b) -> a[0] != b[0] ? a[0] - b[0] : a[1] != b[1] ? a[1] - b[1] : a[2] - b[2]);
        int ans = 0, n = cuboids.length;
        int[] f = new int[n];
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < i; ++j)
                // 排序后，cuboids[j][0] <= cuboids[i][0] 恒成立
                if (cuboids[j][1] <= cuboids[i][1] && cuboids[j][2] <= cuboids[i][2])
                    f[i] = Math.max(f[i], f[j]); // cuboids[j] 可以堆在 cuboids[i] 上
            f[i] += cuboids[i][2];
            ans = Math.max(ans, f[i]);
        }
        return ans;
    }
}

python3 解法, 执行用时: 48 ms, 内存消耗: 14.9 MB, 提交时间: 2022-12-10 11:34:19

class Solution:
    def maxHeight(self, cuboids: List[List[int]]) -> int:
        for c in cuboids:
            c.sort()
        cuboids.sort()
        f = [0] * len(cuboids)
        for i, (_, l2, h2) in enumerate(cuboids):
            for j, (_, l1, h1) in enumerate(cuboids[:i]):
                if l1 <= l2 and h1 <= h2:  # 排序后，w1 <= w2 恒成立
                    f[i] = max(f[i], f[j])  # cuboids[j] 可以堆在 cuboids[i] 上
            f[i] += h2
        return max(f)

上一题

下一题

详情