面试题 08.13. 堆箱子

DP

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
    public int pileBox(int[][] box) {
        Arrays.sort(box, Comparator.comparingInt(o -> o[2]));

        int maxHeightSum = 0;

        // 定义 dp[i] 为截止当前箱子可以堆砌的箱子的最大高度
        int[] dp = new int[box.length];
        for (int i = 0; i < dp.length; i++) { // 注意初始化每个箱子自己的高度为最高高度
            dp[i] = box[i][2];
            maxHeightSum = Math.max(maxHeightSum, dp[i]);
        }

        for (int i = 1; i < box.length; 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]) { // box[j][2] < box[i][2] 防止高度相同
                    dp[i] = Math.max(dp[i], dp[j] + box[i][2]);
                }
            }
            maxHeightSum = Math.max(maxHeightSum, dp[i]);
        }

        return maxHeightSum;
    }
}

DP

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
class Solution {
    public int pileBox(int[][] box) {
        Arrays.sort(box, (o1, o2) -> {
            int diff = o1[2] - o2[2];
            if (diff != 0) {
                return diff;
            } else {
                diff = o2[1] - o1[1]; // 将其他维度值逆序排序可以避免后续处理高度相同的情况
                if (diff != 0) {
                    return diff;
                } else {
                    return o2[0] - o1[0];
                }
            }
        });

        int maxHeightSum = 0;

        // 定义 dp[i] 为截止当前箱子可以堆砌的箱子的最大高度
        int[] dp = new int[box.length];
        for (int i = 0; i < dp.length; i++) { // 注意初始化每个箱子自己的高度为最高高度
            dp[i] = box[i][2];
            maxHeightSum = Math.max(maxHeightSum, dp[i]);
        }

        for (int i = 1; i < box.length; i++) {
            for (int j = 0; j < i; j++) {
                if (box[j][0] < box[i][0] && box[j][1] < box[i][1]) {
                    dp[i] = Math.max(dp[i], dp[j] + box[i][2]);
                }
            }
            maxHeightSum = Math.max(maxHeightSum, dp[i]);
        }

        return maxHeightSum;
    }
}

References

面试题 08.13. 堆箱子