LeetCode 面试题 08.13. 堆箱子

编程基础 • 2024-12-07 18:11 • 阅读 10

文章目录

一、题目
二、C# 题解

一、题目

堆箱子。给你一堆n个箱子，箱子宽 wi、深 di、高 hi。箱子不能翻转，将箱子堆起来时，下面箱子的宽度、高度和深度必须大于上面的箱子。实现一种方法，搭出最高的一堆箱子。箱堆的高度为每个箱子高度的总和。

输入使用数组 [wi, di, hi] 表示每个箱子。

示例1:

输入： box = [[1, 1, 1], [2, 2, 2], [3, 3, 3]]
输出： 6

示例2:

输入： box = [[1, 1, 1], [2, 3, 4], [2, 6, 7], [3, 4, 5]]
输出： 10

提示:

箱子的数目不大于3000个。

此处跳转题目。

二、C# 题解

暴力枚举，但是需要做一些优化，即动态规划。

对箱子严格排序，以减少一层循环
对顺序数组 box，依次求解当以 box_i 为底时的最大高度。伪代码如下

int h = box[i][2]; for (int j = i - 1; j >= 0; j--) { 
    // 就近放置的一种情况 if (box[j] 可放置) { 
    h += box[j][2]; 更新底部为 j; } }

使用 height 数组记录最大高度，height[i] 表示 [0, i] 箱子可堆叠的最大高度，因此上述代码可重复利用 height 以简化循环：

int h = box[i][2]; h += height[j]; // j 为离 i 最近的可放置的箱子序号

考虑到 box_i 为底时，可放置的情况不止一种，需要将所有情况求解后并求 max。所有代码如下

public class Solution { 
    public int PileBox(int[][] box) { 
    // 严格降序，减少后续判断 Array.Sort(box, (a, b) => { 
    if (a[2] != b[2]) return a[2] - b[2]; if (a[1] != b[1]) return a[1] - b[1]; return a[0] - b[0]; }); int[] height = new int[box.Length]; for (int i = 0; i < box.Length; i++) { 
    height[i] = box[i][2]; // 寻找 [0, i) 可放上去的最大值 max int max = 0; for (int j = i - 1; j >= 0; j--) { 
    if (CanPut(box[i], box[j])) max = Math.Max(max, height[j]); } height[i] += max; } return height.Max(); } // 能否将 up 放在 down 上面 public bool CanPut(int[] down, int[] up) => down[2] > up[2] && down[1] > up[1] && down[0] > up[0]; }

时间：132 ms，击败 100.00% 使用 C# 的用户
内存：38.48 MB，击败 100.00% 使用 C# 的用户

今天的文章 LeetCode 面试题 08.13. 堆箱子分享到此就结束了，感谢您的阅读。

LeetCode 面试题 08.13. 堆箱子

文章目录

一、题目

二、C# 题解

相关推荐