leetcode354. 俄罗斯套娃信封问题
| 阿里云国内75折 回扣 微信号：monov8 |
| 阿里云国际，腾讯云国际，低至75折。AWS 93折 免费开户实名账号 代冲值 优惠多多 微信号：monov8 飞机：@monov6 |
思路因为不允许相同宽度或者长度的信封嵌套所以可以先对长度进行升序排序长度相同对宽度进行降序排序
之后再根据宽度计算最长子序列这样就避免了相同的宽度或者长度嵌套。
最后就是经典的计算最长子序列的方法了
def maxEnvelopes(self, envelopes):
"""
:type envelopes: List[List[int]]
:rtype: int
"""
if not envelopes:
return 0
envelopes.sort(key = lambda x: (x[0],-x[-1]))
n = len(envelopes)
stack = [-1]
res = 0
for i in range(n):
if envelopes[i][1] > stack[-1]:
stack.append(envelopes[i][1])
else:
index = bisect.bisect_left(stack,envelopes[i][1])
stack[index] = envelopes[i][1]
return len(stack) - 1
动态规划计算最长子序列超时
def maxEnvelopes(self, envelopes):
"""
:type envelopes: List[List[int]]
:rtype: int
"""
if not envelopes:
return 0
envelopes.sort(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][1] > envelopes[j][1]:
dp[i] = max(dp[i],dp[j]+1)
res = 0
for i in range(n):
res = max(dp[i],res)
return res