给你一个二维整数数组 envelopes ,其中 envelopes[i] = [wi, hi] ,表示第 i 个信封的宽度和高度。 当另一个信封的宽度和高度都比这个信封大的时候,这个信封就可以放进另一个信封里,如同俄罗斯套娃一样。 请计算 最多能有多少个 信封能组成一组“俄罗斯套娃”信封(即可以把一个信封放到另一个信封里面)。 注意:不允许旋转信封。 示例 1: 输入:envelopes = [[5,4],[6,4],[6,7],[2,3]] 输出:3 解释:最多信封的个数为 3, 组合为: [2,3] => [5,4] => [6,7]。 具体的算法
时间: 2023-11-20 09:06:23 浏览: 196
详细的算法步骤如下:
1. 判断输入的envelopes是否为空,若为空则返回0。
2. 对envelopes按照宽度从小到大排序,若宽度相同则按照高度从大到小排列。
3. 定义一个dp数组,其中dp[i]表示以第i个信封为底部的最多嵌套信封数。初始化dp数组为1,因为每个信封本身都可以看作是一个“俄罗斯套娃”信封。
4. 对于dp数组中的每一个元素dp[i],遍历之前的所有信封j,如果envelopes[i]可以嵌套在envelopes[j]中,则有dp[i] = max(dp[i], dp[j] + 1)。
5. 最终,我们需要在dp数组中找到最大值,即为所求的最多能有多少个信封组成一组“俄罗斯套娃”信封。
下面是Python的实现代码:
```
def maxEnvelopes(envelopes: List[List[int]]) -> int:
n = len(envelopes)
if n == 0:
return 0
# 对envelopes按照宽度从小到大排序,若宽度相同则按照高度从大到小排列
envelopes.sort(key=lambda x: (x[0], -x[1]))
# 定义一个dp数组,其中dp[i]表示以第i个信封为底部的最多嵌套信封数
dp = [1] * n
# 遍历dp数组,更新dp[i]的值
for i in range(1, n):
for j in range(i):
if envelopes[i][1] > envelopes[j][1] and envelopes[i][0] > envelopes[j][0]:
dp[i] = max(dp[i], dp[j] + 1)
# 返回dp数组中的最大值
return max(dp)
```
时间复杂度为O(n^2),空间复杂度为O(n)。
阅读全文