354. 俄罗斯套娃信封问题

题目描述

给定一些整数对，(w, h) w 代表信封的宽度，h 代表信封的高度。当一个信封的宽和高都大于另一个信封的时候，就可以把小的放到大的信封中。问 最多 能有多少信封能组成一组 “俄罗斯套娃”

题解

最值问题，使用动态规划，使用前先要对信封排序，按照 从小到大排序。

代码示例

Python 示例

# 超时 84 / 85
class Solution:
    def maxEnvelopes(self, envelopes: List[List[int]]) -> int:
        if not envelopes: return 0 
        envelopes = sorted(envelopes, key=lambda x: (x[0], x[1]))
        n = len(envelopes)
        dp = [1] * n 
        for i in range(n):
            for j in range(i):
                if envelopes[i][0] > envelopes[j][0] and \
                   envelopes[i][1] > envelopes[j][1]:
                    dp[i] = max(dp[i], dp[j] + 1)
        return max(dp)

鉴于Go语言比Python速度快很多，所以果然使用 Go 就可以AC了

Go 示例

func max(a, b int) int {
    if a > b {
        return a
    }
    return b 
}

func maxEnvelopes(envelopes [][]int) int {
    n := len(envelopes)
    if n < 1 {
        return 0
    }

    dp := make([]int, n)
    for i:= 0; i < n; i++ {
        dp[i] = 1
    }

    // 排序  0, 1 都从小到大排序
    sort.Slice(envelopes, func(i, j int) bool {
		if envelopes[i][0] == envelopes[j][0] {
			return envelopes[i][1] < envelopes[j][1]
		}
		return envelopes[i][0] < envelopes[j][0]
	})


    ans := 1
    for i := 0; i < n; i++ {
        for j:= 0; j < i; j++ {
            if envelopes[i][0] > envelopes[j][0] &&
               envelopes[i][1] > envelopes[j][1] {
                   dp[i] = max(dp[i], dp[j] + 1)
                   ans = max(ans, dp[i])
               }   
        }
    }
    return ans
}

优化一，针对递减的 h， 使用动态规划。这里参考 信封嵌套问题 的教程

这个解法的关键在于，对于宽度 w 相同的数对，要对其高度 h 进行降序排序。因为两个宽度相同的信封不能相互包含的，逆序排序保证在 w 相同的数对中最多只选取一个。

# cost 8600 ms
class Solution:
    def maxEnvelopes(self, envelopes: List[List[int]]) -> int:
        if not envelopes: return 0 
        
        # 注意 w从小到大，h从大到小排列
        envelopes = sorted(envelopes, key=lambda x: (x[0], -x[1]))
        n = len(envelopes)
        dp = [1] * n 
        
        # 对 h 求出最长的递增子序列，因为h是递减排序的，是核心思想
        # 如 [1, 1] [1, 2] h是正序的[1, 2] 最长递增子序列是 2，不和题意
        # 当 h 逆序排序的话 [2, 1], 最长递增子序列是 1，符合题意
        dp = [1] * len(envelopes)
        for i in range(1, len(envelopes)):
            for j in range(i):
                if envelopes[i][1] > envelopes[j][1]:
                    dp[i] = max(dp[i], dp[j] + 1)
        return max(dp)

耗时依旧很严重，需要使用 二分查找优化，这个暂时不研究