title
给你一个二维整数数组 envelopes ，其中 envelopes[i] = [wi, hi] ，表示第 i 个信封的宽度和高度。
当另一个信封的宽度和高度都比这个信封大的时候，这个信封就可以放进另一个信封里，如同俄罗斯套娃一样。
请计算 最多能有多少个 信封能组成一组“俄罗斯套娃”信封（即可以把一个信封放到另一个信封里面）。
注意：不允许旋转信封。
示例 1：
输入：envelopes = [[5,4],[6,4],[6,7],[2,3]]
输出：3
解释：最多信封的个数为 3, 组合为: [2,3] => [5,4] => [6,7]。
示例 2：
输入：envelopes = [[1,1],[1,1],[1,1]]
输出：1
提示：
1 <= envelopes.length <= 105envelopes[i].length == 21 <= wi, hi <= 105
solution
其实是个二维的找最长递增子序列，需要a1<a2, b1 < a2 对于[a,b]这样的长宽信封来说。 如果按a有序+ LIS o(nlogn)的模板，会错误的统计到a相同时的结果，所以可以按a有序+按b倒序，这样求b的LIS就是正确的了
class LIS:
# 最长递增子序列长度
def lengthOfLIS(self, nums: List[int]) -> int:
d = []
for n in nums:
# 每个位置存了这个长度结尾的最小元素
if not d or n > d[-1]:
d.append(n)
else:
l, r = 0, len(d) - 1
while l <= r:
mid = (l + r) // 2
if d[mid] >= n:
r = mid - 1
else:
l = mid + 1
d[l] = n
return len(d)
class Solution:
def maxEnvelopes(self, envelopes: List[List[int]]) -> int:
envelopes = sorted(envelopes, key=lambda x: (x[0], -x[1]))
r = LIS().lengthOfLIS([l[1] for l in envelopes])
return r