堆叠长方体的最大高度【LC1691】
Given n cuboids where the dimensions of the ith cuboid is cuboids[i] = [widthi, lengthi, heighti] (0-indexed). Choose a subset of cuboids and place them on each other.
You can place cuboid i on cuboid j if widthi <= widthj and lengthi <= lengthj and heighti <= heightj. You can rearrange any cuboid’s dimensions by rotating it to put it on another cuboid.
Return the maximum height of the stacked cuboids.
啊啊啊 赶紧写完这个本子回家 我要回家！！！！
- 思路：贪心
。局部最优：尽量取最高的边作为长方体的高
。全局最优：堆叠长方体的最大高度最高
- 实现：先将每个长方体的三边从小到大排序，然后将每个长方体根据最长边从大到小排序，然后使用动态规划查找以第i个长方体为顶层的最大高度，最后使用变量记录最大高度
动态规划
1.确定dp数组（dp table）以及下标的含义
dp[i]:以第i个长方体为顶层的最大高度
2.确定递推公式
对于第i个箱子，需要枚举其可能的下一层的长方体j ，经过排序后，即为编号在其之前的长方体
dp[i]=min(dp[i],dp[j]+cuboids[i][2])
3.如何初始化
初始化为每个长方体的最长边
。dp[0]=cuboids[i][2];
4.确定遍历顺序
由dp公式可知，外层正序遍历行i，内层正序遍历列j
5.举例推导dp数组
- 代码
class Solution { public int maxHeight(int[][] cuboids) { int n = cuboids.length; for(int i = 0; i < n; i++){ Arrays.sort(cuboids[i]); } Arrays.sort(cuboids, new Comparator<int[]>(){ public int compare(int[] c1,int []c2){ if (c2[2] == c1[2]){ if (c2[1] == c1[1]){ return c2[0] - c1[0]; }else{ return c2[1] - c1[1]; } } return c2[2] - c1[2]; } }); // Arrays.sort(cuboids, (b, a) -> (a[0] + a[1] + a[2]) - (b[0] + b[1] + b[2])); int[] dp = new int[n]; int ans = 0; for (int i = 0; i < n; i++){ dp[i] = cuboids[i][2]; for (int 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; } }
。复杂度
- 时间复杂度：O ( n 2 ) ，n 为长方体个数
- 空间复杂度：O ( n 2 )
