# 354. 俄罗斯套娃信封问题

[https://leetcode-cn.com/problems/russian-doll-envelopes/](https://leetcode-cn.com/problems/russian-doll-envelopes/)

## 解法一

![alt 属性文本](https://3747312504-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-LXItOiQMDgh0S65YZXd%2Fuploads%2Fgit-blob-df0cc5fb3a72c69e2c0493d1900715a513dcd7b5%2F354_1.jpg?alt=media) ![alt 属性文本](https://3747312504-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-LXItOiQMDgh0S65YZXd%2Fuploads%2Fgit-blob-4e256327c4ebf2b9c9c132ea6de340105d748cf7%2F354_2.jpg?alt=media)

先对宽度 w 进行升序排序，如果遇到 w 相同的情况，则按照高度 h 降序排序。之后把所有的 h 作为一个数组，在这个数组上计算 LIS 的长度就是答案。

```python
class Solution:
    def maxEnvelopes(self, envelopes) -> int:
        def lengthOfLIS(nums):
            n = len(nums)
            maxLen = 0
            dp = [1] * n
            for i in range(n):
                for j in range(i):
                    if nums[i] > nums[j]:
                        dp[i] = max(dp[i], dp[j] + 1)
                maxLen = max(maxLen, dp[i])
            return maxLen

        # 先排序整理，以w为升序，w相等时h降序
        envelopes.sort(key=lambda x: (x[0], -x[1]))
        nums = []
        for e in envelopes:
            nums.append(e[1])
        return lengthOfLIS(nums)
```
