Hard

题目描述

给你 n 个长方体，第 i 个长方体的长宽高分别为 cuboids[i] = [widthi, lengthi, heighti]（下标从 0 开始）。请你从中选出一个子集，按照这些长方体的高度之和的最大值。

如果 widthi <= widthj 且 lengthi <= lengthj 且 heighti <= heightj ，你就可以将长方体 i 放在长方体 j 上。你可以通过旋转把长方体的任意一边作为它的高，宽，或者长。

返回 叠加长方体的最大高度。

示例 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 <= widthi, lengthi, heighti <= 100

解题思路

这是一个经典的动态规划问题，类似于最长递增子序列（LIS）的扩展版本。

核心思路：

  1. 标准化处理：由于长方体可以任意旋转，我们首先将每个长方体的三个维度按升序排列。这样做的目的是让最大的维度作为高度，这样能获得更大的收益。

  2. 排序策略：将所有长方体按照三个维度进行排序。排序的目的是确保如果长方体i可以放在长方体j上面，那么i一定出现在j的后面。

  3. 动态规划：定义 dp[i] 表示以第i个长方体为顶部时能达到的最大高度。状态转移方程为：

    dp[i] = max(dp[j] + height[i])，其中j < i且长方体j可以放在长方体i下面

  4. 可放置条件：长方体j可以放在长方体i下面，当且仅当 cuboids[j][0] <= cuboids[i][0] 且 cuboids[j][1] <= cuboids[i][1] 且 cuboids[j][2] <= cuboids[i][2]。

关键观察：由于可以旋转，我们总是选择最大的维度作为高度，这样能保证获得最优解。排序后的动态规划确保了所有可能的叠放组合都被考虑到。

时间复杂度为O(n²)，空间复杂度为O(n)，适合题目的数据范围。

代码实现

class Solution {
public:
    int maxHeight(vector<vector<int>>& cuboids) {
        // 标准化每个长方体，将三个维度按升序排列
        for (auto& cuboid : cuboids) {
            sort(cuboid.begin(), cuboid.end());
        }
        
        // 对所有长方体进行排序
        sort(cuboids.begin(), cuboids.end());
        
        int n = cuboids.size();
        vector<int> dp(n);
        
        // 初始化dp数组，每个长方体单独时的高度
        for (int i = 0; i < n; i++) {
            dp[i] = cuboids[i][2]; // 最大维度作为高度
        }
        
        // 动态规划
        for (int i = 1; i < n; i++) {
            for (int j = 0; j < i; j++) {
                // 检查长方体j是否可以放在长方体i下面
                if (cuboids[j][0] <= cuboids[i][0] && 
                    cuboids[j][1] <= cuboids[i][1] && 
                    cuboids[j][2] <= cuboids[i][2]) {
                    dp[i] = max(dp[i], dp[j] + cuboids[i][2]);
                }
            }
        }
        
        // 返回最大高度
        return *max_element(dp.begin(), dp.end());
    }
};

class Solution:
    def maxHeight(self, cuboids: List[List[int]]) -> int:
        # 标准化每个长方体，将三个维度按升序排列
        for cuboid in cuboids:
            cuboid.sort()
        
        # 对所有长方体进行排序
        cuboids.sort()
        
        n = len(cuboids)
        dp = [0] * n
        
        # 初始化dp数组，每个长方体单独时的高度
        for i in range(n):
            dp[i] = cuboids[i][2]  # 最大维度作为高度
        
        # 动态规划
        for i in range(1, n):
            for j in range(i):
                # 检查长方体j是否可以放在长方体i下面
                if (cuboids[j][0] <= cuboids[i][0] and 
                    cuboids[j][1] <= cuboids[i][1] and 
                    cuboids[j][2] <= cuboids[i][2]):
                    dp[i] = max(dp[i], dp[j] + cuboids[i][2])
        
        # 返回最大高度
        return max(dp)

public class Solution {
    public int MaxHeight(int[][] cuboids) {
        // 标准化每个长方体，将三个维度按升序排列
        foreach (var cuboid in cuboids) {
            Array.Sort(cuboid);
        }
        
        // 对所有长方体进行排序
        Array.Sort(cuboids, (a, b) => {
            for (int i = 0; i < 3; i++) {
                int cmp = a[i].CompareTo(b[i]);
                if (cmp != 0) return cmp;
            }
            return 0;
        });
        
        int n = cuboids.Length;
        int[] dp = new int[n];
        
        // 初始化dp数组，每个长方体单独时的高度
        for (int i = 0; i < n; i++) {
            dp[i] = cuboids[i][2]; // 最大维度作为高度
        }
        
        // 动态规划
        for (int i = 1; i < n; i++) {
            for (int j = 0; j < i; j++) {
                // 检查长方体j是否可以放在长方体i下面
                if (cuboids[j][0] <= cuboids[i][0] && 
                    cuboids[j][1] <= cuboids[i][1] && 
                    cuboids[j][2] <= cuboids[i][2]) {
                    dp[i] = Math.Max(dp[i], dp[j] + cuboids[i][2]);
                }
            }
        }
        
        // 返回最大高度
        return dp.Max();
    }
}

var maxHeight = function(cuboids) {
    // 标准化每个长方体，将三个维度按升序排列
    for (let cuboid of cuboids) {
        cuboid.sort((a, b) => a - b);
    }
    
    // 对所有长方体进行排序
    cuboids.sort((a, b) => {
        for (let i = 0; i < 3; i++) {
            if (a[i] !== b[i]) {
                return a[i] - b[i];
            }
        }
        return 0;
    });
    
    const n = cuboids.length;
    const dp = new Array(n);
    
    // 初始化dp数组，每个长方体单独时的高度
    for (let i = 0; i < n; i++) {
        dp[i] = cuboids[i][2]; // 最大维度作为高度
    }
    
    // 动态规划
    for (let i = 1; i < n; i++) {
        for (let j = 0; j < i; j++) {
            // 检查长方体j是否可以放在长方体i下面
            if (cuboids[j][0] <= cuboids[i][0] && 
                cuboids[j][1] <= cuboids[i][1] && 
                cuboids[j][2] <= cuboids[i][2]) {
                dp[i] = Math.max(dp[i], dp[j] + cuboids[i][2]);
            }
        }
    }
    
    // 返回最大高度
    return Math.max(...dp);
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型大小
时间复杂度O(n²)
空间复杂度O(n)

其中 n 是长方体的数量。时间复杂度主要来自于嵌套循环的动态规划过程，空间复杂度来自于dp数组的存储。

相关题目