面试题 08.13. 堆箱子

题目描述

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

输入使用数组[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个。

解法

方法一：排序 + 动态规划

我们先将箱子按照宽度升序、深度降序的顺序进行排序，然后使用动态规划求解。

定义 $f[i]$ 表示以第 $i$ 个箱子为底部的最大高度。对于 $f[i]$，我们枚举 $j \in [0, i)$，如果 $box[j][1] \lt box[i][1]$ 且 $box[j][2] \lt box[i][2]$，那么我们可以将第 $j$ 个箱子放在第 $i$ 个箱子上面，此时 $f[i] = \max{f[i], f[j]}$。最后我们将 $f[i]$ 加上第 $i$ 个箱子的高度，即可得到 $f[i]$ 的最终值。

答案为 $f$ 中的最大值。

时间复杂度 $O(n^2)$，空间复杂度 $O(n)$。其中 $n$ 是箱子的数目。

Python3JavaC++GoTypeScriptSwift

class Solution:
    def pileBox(self, box: List[List[int]]) -> int:
        box.sort(key=lambda x: (x[0], -x[1]))
        n = len(box)
        f = [0] * n
        for i in range(n):
            for j in range(i):
                if box[j][1] < box[i][1] and box[j][2] < box[i][2]:
                    f[i] = max(f[i], f[j])
            f[i] += box[i][2]
        return max(f)

class Solution {
    public int pileBox(int[][] box) {
        Arrays.sort(box, (a, b) -> a[0] == b[0] ? b[1] - a[1] : a[0] - b[0]);
        int n = box.length;
        int[] f = new int[n];
        int ans = 0;
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < i; ++j) {
                if (box[j][1] < box[i][1] && box[j][2] < box[i][2]) {
                    f[i] = Math.max(f[i], f[j]);
                }
            }
            f[i] += box[i][2];
            ans = Math.max(ans, f[i]);
        }
        return ans;
    }
}

class Solution {
public:
    int pileBox(vector<vector<int>>& box) {
        sort(box.begin(), box.end(), [](const vector<int>& a, const vector<int>& b) {
            return a[0] < b[0] || (a[0] == b[0] && b[1] < a[1]);
        });
        int n = box.size();
        int f[n];
        memset(f, 0, sizeof(f));
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < i; ++j) {
                if (box[j][1] < box[i][1] && box[j][2] < box[i][2]) {
                    f[i] = max(f[i], f[j]);
                }
            }
            f[i] += box[i][2];
        }
        return *max_element(f, f + n);
    }
};

func pileBox(box [][]int) int {
    sort.Slice(box, func(i, j int) bool {
        a, b := box[i], box[j]
        return a[0] < b[0] || (a[0] == b[0] && b[1] < a[1])
    })
    n := len(box)
    f := make([]int, n)
    for i := 0; i < n; i++ {
        for j := 0; j < i; j++ {
            if box[j][1] < box[i][1] && box[j][2] < box[i][2] {
                f[i] = max(f[i], f[j])
            }
        }
        f[i] += box[i][2]
    }
    return slices.Max(f)
}

function pileBox(box: number[][]): number {
    box.sort((a, b) => (a[0] === b[0] ? b[1] - a[1] : a[0] - b[0]));
    const n = box.length;
    const f: number[] = new Array(n).fill(0);
    let ans: number = 0;
    for (let i = 0; i < n; ++i) {
        for (let j = 0; j < i; ++j) {
            if (box[j][1] < box[i][1] && box[j][2] < box[i][2]) {
                f[i] = Math.max(f[i], f[j]);
            }
        }
        f[i] += box[i][2];
        ans = Math.max(ans, f[i]);
    }
    return ans;
}

class Solution {
    func pileBox(_ box: [[Int]]) -> Int {
        let boxes = box.sorted {
            if $0[0] == $1[0] {
                return $0[1] > $1[1]
            } else {
                return $0[0] < $1[0]
            }
        }

        let n = boxes.count
        var f = Array(repeating: 0, count: n)
        var ans = 0

        for i in 0..<n {
            f[i] = boxes[i][2]
            for j in 0..<i {
                if boxes[j][1] < boxes[i][1] && boxes[j][2] < boxes[i][2] {
                    f[i] = max(f[i], f[j] + boxes[i][2])
                }
            }
            ans = max(ans, f[i])
        }

        return ans
    }
}

面试题 08.13. 堆箱子

题目描述

解法

方法一：排序 + 动态规划

评论