盒子堆叠问题

17 Mar 2025 | 4 分钟阅读

问题陈述

您将获得三个大小为 N 的整数数组，分别代表 N 个盒子的 H、W 和 L（高、宽、长）。

您的任务是将这些盒子堆叠起来，以达到最大的高度，并且您需要返回该最大高度。

要将一个盒子放在另一个盒子的顶部，顶盒的尺寸必须严格小于底盒的尺寸，这意味着顶盒的长和宽必须严格小于底盒的长和宽。

我们可以有多个盒子的实例，这意味着我们可以随意旋转盒子，然后将其用作另一个盒子。我们知道一个长方体有六个面。我们可以有六个盒子的实例，但只有三个唯一的实例，所以间接来说，我们将有 3*N 个具有不同尺寸的盒子，并且我们需要找到最大高度。

方法

我们将使用动态规划方法来解决这个问题。我们将根据宽度对数组进行排序，然后尝试找出最长递增子序列 (LIS) 来获得最大高度。

Java 示例

import java.util.*;
public class Main{
    public static class Pair implements Comparable<Pair>{
        int h;
        int w;
        int l;
        Pair(int h,int w,int l){
            this.h=h;
            this.w=w;
            this.l=l;
        }
        public int compareTo(Pair o){
            if(this.w==o.w)
            return o.l-this.l;
            return this.w-o.w;
        }
    }
    public static void main(String[] args){
        int[] height={4,1,4,10};
        int[] width={6,2,5,12};
        int[] length={7,3,6,32};
        
        System.out.println(getHeight(height,width,length));
    }
    public static int getHeight(int[] height,int[] width,int[] length){
        ArrayList<Pair> arr = new ArrayList<>();
        for(int i=0;i<height.length;i++){
            if(width[i]<length[i]){
                arr.add(new Pair(height[i],width[i],length[i]));
            }else{
                arr.add(new Pair(height[i],length[i],width[i]));
            }
            
            if(height[i]<length[i]){
                 arr.add(new Pair(width[i],height[i],length[i]));
            }else{
                arr.add(new Pair(width[i],length[i],height[i]));
            }
            
            if(height[i]<width[i]){
                arr.add(new Pair(length[i],height[i],width[i]));
            }else{
                arr.add(new Pair(length[i],width[i],height[i]));
            }
        }
        Collections.sort(arr);
        int[] dp=new int[arr.size()];
        int ans=0;
        for(int i=0;i<dp.length;i++){
            if(i==0){
                dp[i]=arr.get(i).h;
                ans=Math.max(ans,dp[i]);
                continue;
            }
            int max=0;
            for(int j=0;j<i;j++){
                if(arr.get(j).l< arr.get(i).l && arr.get(j).w<arr.get(i).w)
                max=Math.max(max,dp[j]);
            }
            dp[i]=arr.get(i).h+max;
            ans=Math.max(ans,dp[i]);
        }
        return ans;
    }
   
}

输出

解释

在上面的代码中，我们有三个不同的数组，分别代表四个不同盒子的 H、W 和 L。如我们所知，我们可以旋转盒子来创建它的实例，所以间接来说，我们将为这个问题提供 12 个选项或 12 个盒子。

我们将创建 pair 类来存储尺寸，并为我们的 ArrayList 编写比较器。我们将遍历数组，并将为每个盒子检查三种情况以获得其三个实例。

情况 1：如果盒子的宽度小于长度，那么我们将按原样添加尺寸。否则，我们将宽度与长度交换并将其添加为一个新盒子。

情况 2：如果盒子的高度小于长度，那么我们将交换高度和宽度；否则，我们将宽度与高度交换，然后再次将高度与长度交换，并将其添加为一个新盒子。

情况 3：如果盒子的高度小于宽度，那么我们将交换宽度和长度，然后交换长度和高度以获得新的尺寸盒子。否则，我们将高度与长度交换，并将其添加为一个新盒子。

在将所有相关的盒子添加到 ArrayList 后，我们将根据它们的宽度按升序对它们进行排序。

我们将使用 LIS（最长递增子序列）技术来获得解决方案。我们将创建一个大小与 ArrayList 相同的 dp 数组。

dp[i] 将存储通过堆叠从 0 到 i-1 的盒子所能获得的最大高度，前提是栈的底部是第 i 个盒子。

如果是第一个盒子，那么最大高度将是它本身的高度，这将是基本情况。

现在对于其余的盒子，我们将从 0 循环到 i-1，并获得 dp[j] 的最大值，然后我们将最大值和第 i 个盒子的高度相加，以获得盒子的最大尺寸。

dp 数组的最大值将是我们的答案。

在上面的示例中，我们有四个盒子，因此我们将创建它的 12 个实例，如下所示

盒子编号	高度	宽度	length
1	4	6	7
2	6	4	7
3	7	4	6
4	1	2	3
5	2	1	3
6	3	1	2
7	4	5	6
8	5	4	6
9	6	4	5
10	10	12	32
11	12	10	32
12	32	10	12

时间复杂度：O(N²)

空间复杂度：O(N)

下一个主题Java 中的 K 个最频繁元素

盒子堆叠问题

问题陈述

方法

Java 示例

联系信息

关注我们

教程

面试题

在线编译器

Python

Java

.Net Framework

AI, ML and Data Science

Cloud Technology

B.Tech and MCA

Web Technology

PHP

Software Testing

Technical Interview

Java Interview

Python

Web Interview

Database Interview

B.Tech / MCA

Important Interview

Software Testing Interview

Company Interviews

Online Compilers

Multiple Choice Questions

Java Conversion

Java Misc

盒子堆叠问题

问题陈述

方法

Java 示例

相关帖子

Find the Largest Palindrome Divisible by K in Java

Difference Bitwise AND (&) and Logical AND (&&) in Java

Smith Number in Java

The Celebrity Problem in Java

Java 中字节码和机器码的区别

在 Java 中反转二叉树

Java 中的字符串压缩问题

Java 和 Apache OpenNLP

Java 12 中的 Switch Case

Java 中的 DAO 类

订阅 Tpoint Tech

联系信息

关注我们

教程

面试题

在线编译器