我的博客

Leetcode 354. 俄罗斯套娃信封问题 Russian Doll Envelopes

目录

https://leetcode-cn.com/problems/russian-doll-envelopes

这道题目用了巧妙的方法,关于 lengthOfLIS 函数可以参见 300. 最长上升子序列的解答 这个函数就是从这个题目中复制过来的。

本题目用了一个巧妙的方法处理信封顺序。信封的宽度是按升序排序,但是宽度相同时却按高度的降序排序。

这是因为宽度相同的信封无法套娃,所以这时把高度按降序排列,就无法利用同宽度的信封了。由于传入 lengthOfLIS 函数的只有高度信息,这种排序方法相当于把宽度信息传递到高度中了(通过把同宽度的信封高度按逆序排列)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
import bisect
class Solution:
def lengthOfLIS(self, nums: List[int]) -> int:
dp = []
for i in range(len(nums)):
idx = bisect.bisect_left(dp, nums[i])
if idx == len(dp):
dp.append(nums[i])
else:
dp[idx] = nums[i]
return len(dp)

def maxEnvelopes(self, envelopes: List[List[int]]) -> int:
if not envelopes:
return 0
envelopes.sort(key=lambda x:(x[0], -x[1]))
return self.lengthOfLIS([x[1] for x in envelopes])

欢迎来我的博客: https://codeplot.top/
我的博客刷题分类:https://codeplot.top/categories/%E5%88%B7%E9%A2%98/

评论无需登录,可以匿名,欢迎评论!