首页
学习
活动
专区
圈层
工具
发布
社区首页 >专栏 >LeetCode 1691. 堆叠长方体的最大高度(排序+最大上升子序DP)

LeetCode 1691. 堆叠长方体的最大高度(排序+最大上升子序DP)

作者头像
Michael阿明
发布于 2021-02-19 14:58:47
发布于 2021-02-19 14:58:47
1.3K0
举报

文章目录

463 / 3709,前 12.5%

1240 / 9290,前13.3%

1. 题目

给你 n 个长方体 cuboids ,其中第 i 个长方体的长宽高表示为 cuboids[i] = [widthi, lengthi, heighti](下标从 0 开始)。请你从 cuboids 选出一个 子集 ,并将它们堆叠起来。

如果 widthi <= widthj 且 lengthi <= lengthj 且 heighti <= heightj ,你就可以将长方体 i 堆叠在长方体 j 上。你可以通过旋转把长方体的长宽高重新排列,以将它放在另一个长方体上。

返回 堆叠长方体 cuboids 可以得到的 最大高度 。

示例 1:

代码语言:javascript
复制
输入: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

来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/maximum-height-by-stacking-cuboids 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

2. 解题

2.1 暴力超时解

  • 复杂度太高了,超时
代码语言:javascript
复制
class Solution {
public:
    int maxHeight(vector<vector<int>>& cub) {
        sort(cub.begin(), cub.end(),[&](auto& a, auto& b){
            return a[0]+a[1]+a[2] < b[0]+b[1]+b[2];
        });
        int n = cub.size();
        vector<vector<vector<int>>> dp(101,vector<vector<int>>(101, vector<int>(101, -1)));
        dp[0][0][0] = 0;
        dp[cub[0][0]][cub[0][1]][cub[0][2]] = max(dp[cub[0][0]][cub[0][1]][cub[0][2]],cub[0][2]);
        dp[cub[0][0]][cub[0][2]][cub[0][1]] = max(dp[cub[0][0]][cub[0][2]][cub[0][1]],cub[0][1]);
        dp[cub[0][1]][cub[0][0]][cub[0][2]] = max(dp[cub[0][1]][cub[0][0]][cub[0][2]],cub[0][2]);
        dp[cub[0][2]][cub[0][0]][cub[0][1]] = max(dp[cub[0][2]][cub[0][0]][cub[0][1]],cub[0][1]);
        dp[cub[0][1]][cub[0][2]][cub[0][0]] = max(dp[cub[0][1]][cub[0][2]][cub[0][0]],cub[0][0]);
        dp[cub[0][2]][cub[0][1]][cub[0][0]] = max(dp[cub[0][2]][cub[0][1]][cub[0][0]],cub[0][0]);
        for(int i = 1; i < n; ++i)
        {
            vector<vector<vector<int>>> temp(dp.begin(), dp.end());
            int a = cub[i][0], b = cub[i][1], c = cub[i][2];
            for(int w = 0; w <= 100; ++w)
            {
                for(int l = 0; l <= 100; ++l)
                {
                    for(int h = 0; h <= 100; ++h)
                    {
                        if(temp[w][l][h] == -1)
                            continue;
                        if(a >= w && b >= l && c >= h)
                            temp[a][b][c] = max(temp[a][b][c], dp[w][l][h]+c);
                        if(b >= w && a >= l && c >= h)
                            temp[b][a][c] = max(temp[b][a][c], dp[w][l][h]+c);
                        if(a >= w && c >= l&& b >= h)
                            temp[a][c][b] = max(temp[a][c][b], dp[w][l][h]+b);
                        if(c >= w && a >= l&& b >= h)
                            temp[c][a][b] = max(temp[c][a][b], dp[w][l][h]+b);
                        if(b >= w && c >=l&& a >= h)
                            temp[b][c][a] = max(temp[b][c][a], dp[w][l][h]+a);
                        if(c >= w && b >=l&& a >= h)
                            temp[c][b][a] = max(temp[c][b][a], dp[w][l][h]+a);
                    }
                }
            }
            dp = temp;
        }
        int ans = 0;
        for(int h = 1; h <= 100; h++)
            for(int w = 1; w <= 100; ++w)
            {
                for(int l = 1; l <= 100; ++l)
                {
                    ans = max(ans, dp[w][l][h]);
                }
            }
        return ans;
    }
};

2.2 排序+最长上升子序

  • 先对每个长方体的长宽高排序
  • 再对所有长方体按照(长宽高)排序
  • 再利用最长上升子序DP
代码语言:javascript
复制
class Solution {
public:
    int maxHeight(vector<vector<int>>& cub) {
        vector<vector<int>> C(6, vector<int>(3));
        C[0] = {0,1,2};
        C[1] = {0,2,1};
        C[2] = {1,0,2};
        C[3] = {1,2,0};
        C[4] = {2,0,1};
        C[5] = {2,1,0};//最后一维是高度维
        for(auto& c : cub)
            sort(c.begin(), c.end());
        sort(cub.begin(), cub.end());
        int n = cub.size();
        vector<vector<int>> dp(n, vector<int>(6, 0));
        dp[0][0] = cub[0][C[0][2]];
        dp[0][1] = cub[0][C[1][2]];
        dp[0][2] = cub[0][C[2][2]];
        dp[0][3] = cub[0][C[3][2]];
        dp[0][4] = cub[0][C[4][2]];
        dp[0][5] = cub[0][C[5][2]];
        
        for(int i = 1; i < n; ++i)
        {
            for(int c1 = 0; c1 < 6; ++c1)
            {
                dp[i][c1] = cub[i][C[c1][2]];//初始化为自己的高度
                for(int j = 0; j < i; ++j)
                {
                    for(int c2 = 0; c2 < 6; ++c2)
                    {   
                        if(cub[j][C[c2][0]] <= cub[i][C[c1][0]]
                            && cub[j][C[c2][1]] <= cub[i][C[c1][1]]
                            && cub[j][C[c2][2]] <= cub[i][C[c1][2]])
                        {
                            dp[i][c1] = max(dp[i][c1], dp[j][c2]+cub[i][C[c1][2]]);
                        }
                    }
                }
            }
        }
        int ans = 0;
        for(int i = 0; i < n; i++)
        {
            for(int k = 0; k < 6; k++)
            {
                ans = max(ans, dp[i][k]);
            }
        }
        return ans;
    }
};

332 ms 9.8 MB C++


​

​

本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2020/12/13 ,如有侵权请联系 cloudcommunity@tencent.com 删除
目录
  • 文章目录
  • 1. 题目
  • 2. 解题
    • 2.1 暴力超时解
    • 2.2 排序+最长上升子序
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档