LeetCode 面试题 08.13. 堆箱子

Categories:

题目描述
思路分析
1. 解法一：排序 + 动态规划（推荐）
相似题目

题目描述

✅ 面试题 08.13. 堆箱子

思路分析

解法一：排序 + 动态规划（推荐）

核心思路：

先按长、宽、高升序排序，确保枚举到第 i 个箱子时，可能放在其下方的箱子都在 i 之前。

设 dp[i] 表示以第 i 个箱子作为最上层时可获得的最大高度。

枚举 i 之前所有箱子 j，若三维均严格小于 i，则尝试转移：dp[i] = max(dp[i], dp[j] + h[i])。

复杂度分析：

时间复杂度：O(n^2)，其中 n 表示箱子数量。

空间复杂度：O(n)，用于保存 dp 数组。

import java.util.Arrays;

class Solution {
    public int pileBox(int[][] box) {
        if (box == null || box.length == 0) {
            return 0;
        }

        // 按三维升序排序，保证转移只需看 i 之前
        Arrays.sort(box, (a, b) -> {
            if (a[0] != b[0]) {
                return a[0] - b[0];
            }
            if (a[1] != b[1]) {
                return a[1] - b[1];
            }
            return a[2] - b[2];
        });

        int n = box.length;
        int[] dp = new int[n];
        int res = 0;

        // dp[i] 表示以第 i 个箱子为顶的最大高度
        for (int i = 0; i < n; i++) {
            dp[i] = box[i][2];

            // 枚举可放在 i 下方的箱子
            for (int j = 0; j < i; j++) {
                if (box[j][0] < box[i][0]
                        && box[j][1] < box[i][1]
                        && box[j][2] < box[i][2]) {
                    dp[i] = Math.max(dp[i], dp[j] + box[i][2]);
                }
            }

            res = Math.max(res, dp[i]);
        }

        return res;
    }
}

import "sort"

func pileBox(box [][]int) int {
	if len(box) == 0 {
		return 0
	}

	// 按三维升序排序，保证转移只需看 i 之前
	sort.Slice(box, func(i, j int) bool {
		if box[i][0] != box[j][0] {
			return box[i][0] < box[j][0]
		}
		if box[i][1] != box[j][1] {
			return box[i][1] < box[j][1]
		}
		return box[i][2] < box[j][2]
	})

	n := len(box)
	dp := make([]int, n)
	res := 0

	// dp[i] 表示以第 i 个箱子为顶的最大高度
	for i := 0; i < n; i++ {
		dp[i] = box[i][2]

		// 枚举可放在 i 下方的箱子
		for j := 0; j < i; j++ {
			if box[j][0] < box[i][0] && box[j][1] < box[i][1] && box[j][2] < box[i][2] {
				if dp[j]+box[i][2] > dp[i] {
					dp[i] = dp[j] + box[i][2]
				}
			}
		}

		if dp[i] > res {
			res = dp[i]
		}
	}

	return res
}

相似题目

题目	难度	考察点
300. 最长递增子序列	中等	动态规划、序列优化
354. 俄罗斯套娃信封问题	困难	排序 + LIS
1691. 堆叠长方体的最大高度	困难	排序 + 动态规划
673. 最长递增子序列的个数	中等	动态规划、计数
646. 最长数对链	中等	贪心、LIS

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2026/24544463