題目

給你 n 個長方體 cuboids ，

其中第 i 個長方體的長寬高表示為 cuboids[i] = [widthi, lengthi, heighti]（下標從 0 開始）。

請你從 cuboids 選出一個 子集 ，並將它們堆疊起來。

如果 widthi <= widthj 且 lengthi <= lengthj 且 heighti <= heightj ，

你就可以將長方體 i 堆疊在長方體 j 上。你可以透過旋轉把長方體的長寬高重新排列，以將它放在另一個長方體上。

返回 堆疊長方體 cuboids 可以得到的 最大高度 。

示例 1：輸入：cuboids = [[50,45,20],[95,37,53],[45,23,12]] 輸出：190

解釋：第 1 個長方體放在底部，53x37 的一面朝下，高度為 95 。

第 0 個長方體放在中間，45x20 的一面朝下，高度為 50 。

第 2 個長方體放在上面，23x12 的一面朝下，高度為 45 。

總高度是 95 + 50 + 45 = 190 。

示例 2：輸入：cuboids = [[38,25,45],[76,35,3]] 輸出：76

解釋：無法將任何長方體放在另一個上面。

選擇第 1 個長方體然後旋轉它，使 35x3 的一面朝下，其高度為 76 。

示例 3：輸入：cuboids = [[7,11,17],[7,17,11],[11,7,17],[11,17,7],[17,7,11],[17,11,7]]

輸出：102

解釋：重新排列長方體後，可以看到所有長方體的尺寸都相同。

你可以把 11x7 的一面朝下，這樣它們的高度就是 17 。

堆疊長方體的最大高度為 6 * 17 = 102 。

提示：n == cuboids.length

1 <= n <= 100

1 <= widthi, lengthi, heighti <= 100

解題思路分析

1、排序+動態規劃；時間複雜度O(n^2)，空間複雜度O(n)

func maxHeight(cuboids [][]int) int {	for i := 0; i < len(cuboids); i++ {		arr := cuboids[i]		sort.Ints(arr)		cuboids[i] = arr	}	sort.Slice(cuboids, func(i, j int) bool {		if cuboids[i][0] == cuboids[j][0] {			if cuboids[i][1] == cuboids[j][1] {				return cuboids[i][2] < cuboids[j][2]			}			return cuboids[i][1] < cuboids[j][1]		}		return cuboids[i][0] < cuboids[j][0]	})	n := len(cuboids)	dp := make([]int, n)	for i := 0; i < n; i++ {		dp[i] = cuboids[i][2]	}	res := dp[0]	for i := 1; i < n; i++ {		for j := 0; j < i; j++ {			if cuboids[i][0] >= cuboids[j][0] &&				cuboids[i][1] >= cuboids[j][1] &&				cuboids[i][2] >= cuboids[j][2] {				dp[i] = max(dp[i], dp[j]+cuboids[i][2])			}		}		res = max(res, dp[i])	}	return res}func max(a, b int) int {	if a > b {		return a	}	return b}

總結

Hard題目，需要先排序，然後轉換位3維最長子序列問題，題目思路是動態規劃，參考leetcode 300.最長上升子序列leetcode 354.俄羅斯套娃信封問題