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

目录

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

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

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

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

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/