)
class Solution {
public int maxHeight(int[][] cuboids) {
int n = cuboids.length;
// 1. 对每个长方体的长宽高进行排序，保证 cuboid[i][0] {
if (a[0] != b[0]) {
return a[0] - b[0];
} else if (a[1] != b[1]) {
return a[1] - b[1];
} else {
return a[2] - b[2];
}
});
// 3. 动态规划
// dp[i] 表示以第 i 个长方体为底部时，能够堆叠出的最大高度
int[] dp = new int[n];
int maxAns = 0;
for (int i = 0; i < n; i++) {
// 初始化：至少可以放自己，高度为自身的最长边（即 cuboids[i][2]）
dp[i] = cuboids[i][2];
// 状态转移：检查所有在 i 之前的长方体 j
// 如果长方体 j 可以放在长方体 i 的上面，则更新 dp[i]
for (int j = 0; j < i; j++) {
// 由于已经排序，cuboids[j][0] <= cuboids[i][0] 恒成立
// 只需要判断另外两个维度
if (cuboids[j][1] <= cuboids[i][1] && cuboids[j][2] <= cuboids[i][2]) {
dp[i] = Math.max(dp[i], dp[j] + cuboids[i][2]);
}
}
// 更新全局最大高度
maxAns = Math.max(maxAns, dp[i]);
}
return maxAns;
}
}
