首页 > 其他分享 >力扣每日一题2022.12.10---1691. 堆叠长方体的最大高度

力扣每日一题2022.12.10---1691. 堆叠长方体的最大高度

时间:2022-12-10 23:46:26浏览次数:92  
标签:11 10 17 int 高度 --- 长方体 cuboids

给你 n 个长方体 cuboids ,其中第 i 个长方体的长宽高表示为 cuboids[i] = [widthi, lengthi, heighti](下标从 0 开始)。请你从 cuboids 选出一个 子集 ,并将它们堆叠起来。
如果 widthi <= widthj 且 lengthi <= lengthj 且 heighti <= heightj ,你就可以将长方体 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 <= widthi, lengthi, heighti <= 100

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

 

解题难点还是在思路上,即什么情况下是最优解。

算法主要还是动态规划的思想,关于代码的部分放注释了。

 1 class Solution {
 2     public int maxHeight(int[][] cuboids) {
 3         for (int[] v : cuboids) {
 4             Arrays.sort(v);
 5         }
 6         //给cuboids数组中的每一个一维数组从小到大排序。
 7         Arrays.sort(cuboids, (a, b) -> (a[0] + a[1] + a[2]) - (b[0] + b[1] + b[2]));
 8         //对二维数组进行排序,排序的规则是按照每个一维数组和的大小。
 9         int ans = 0;
10         int len = cuboids.length;
11         int[] dp = new int[len];
12         //保存每一个位置的最优解
13         for (int i = 0; i < len; i ++) {
14             dp[i] = cuboids[i][2];
15             //dp[i]表示第i个位置的最大高度。
16             for (int j = 0; j < i; j ++) {
17                 if (cuboids[j][0] <= cuboids[i][0] &&
18                         cuboids[j][1] <= cuboids[i][1] &&
19                         cuboids[j][2] <= cuboids[i][2]) {
20                     dp[i] = Math.max(dp[i], dp[j] + cuboids[i][2]);
21                     //由if的判断条件可知,第j个肯定能够放在第i个的位置,那么,此时的高度为第j个的高度加第i个的高度。可能有多个j,取其中的最大值即可。
22                 }
23             }
24             ans = Math.max(ans, dp[i]);
25         }
26         return ans;
27     }
28 }

 

标签:11,10,17,int,高度,---,长方体,cuboids
From: https://www.cnblogs.com/allWu/p/16972627.html

相关文章

  • k8s--数据存储、PV、PVC
    介绍在前面学了使用NFS提供存储,此时就要求用户会搭建NFS系统,并且会在yaml中配置nfs。由于kubernetes支持的存储系统有很多,要求客户全都掌握,显然不合理。为了能够......
  • Go-14 Golang语言中 函数详解之defer延迟处理函数和return的结合使用
    packagemain//defer延迟处理函数和return的结合运用/* 按照下面的示例作了一个总结,文字结合下面的代码更容易理解 总结一下规则: defer里面的变量必须与函数定义的......
  • #yyds干货盘点#【愚公系列】2022年12月 微信小程序-纵向和横向选项卡功能实现
    前言纵向选项卡(vtabs)用于让用户在不同的视图中进行切换。以下讲解的是weui版,相关的还有antd-mini版本:https://help.aliyun.com/document_detail/438087.html一、纵向选......
  • Docker数据卷容器(volumes-from)
    前戏由于项目过多导致持久化挂载过多,后面使用容器来实现数据挂载及共享。。。介绍数据卷容器:​​命名的容器挂载数据卷,其它容器通过挂载这个(父容器)实现数据共享,挂载数据卷......
  • 详解逻辑回归与评分卡-梯度下降求解逻辑回归【菜菜的sklearn课堂笔记】
    视频作者:菜菜TsaiTsai链接:【技术干货】菜菜的机器学习sklearn【全85集】Python进阶_哔哩哔哩_bilibili我们以最著名也最常用的梯度下降法为例。现在有一个带两个特征并......
  • abc--281--F
    F-XorMinimization思路感觉算是字典树的板子题了先对每一个数进行按位分解,然后看这一位可以选择什么如果这一位既有0,又有1,那么这一定是1否则就可以为0,走为0的这条......
  • ATPCS规则 ------ 汇编传参规则
    1、寄存器使用规则ARM处理器中有r0-r15共16个寄存器,它们的用途有一些约定的习惯,并依据这些用途定义了别名,如表所示。项目别名使用规则r15pc程序计数器r14lr......
  • 《Emergent Cooperation from Mutual Acknowledgment Exchange》 2022-AAMAS
    从相互交换确认中产生合作总结:为了改进传统的激励其他代理人机制,其存在隐私侵犯的问题,文中提出一种两阶段的请求和回应机制,即即使想要激励其他人送出的东西还需要得到......
  • Atcoder-ABC281-DEF题解
    AtcoderBeginnerContest281D.MaxMultiple(DP)题意在长度为\(N\)的序列\(A\)中,找到\(K\)个元素其和为\(D\)的倍数,找出满足要求最大的和,没有则返回-1。数......
  • S1 - Lesson 85 - 86
    Words Paris cinema filmmoviegotothecinemawatchafilmwatchamovie beautifulnicesmartlovelygood-lookinggorgeousbeauty cityNewYork......