难度: Hard
给你一个二维整数数组 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运行时间: 164 ms
内存: 0.0 MB
class Solution:
def maxEnvelopes(self, envelopes: List[List[int]]) -> int:
def LIS(nums):
n = len(nums)
if n < 2: return 1
dp = [0] * n
maxL = 0
for num in nums:
left, right = 0, maxL
while left < right:
mid = left + (right - left)//2
if dp[mid] < num:
left = mid + 1
else: right = mid
dp[left] = num
if left == maxL: maxL += 1
return maxL
if not envelopes or not len(envelopes): return 0
envelopes.sort(key=lambda x: (x[0], -x[1]))
weights = [i[1] for i in envelopes]
return LIS(weights)
这个题解的思路是先按宽度升序和高度降序对信封进行排序，然后对排序后的信封高度数组求最长上升子序列（LIS）。这样做的原因是，对于宽度相同的信封，我们只需保留高度最小的，因为其他的信封都可以套在高度最小的信封外面。排序后，问题就转化为在高度数组上求LIS，而LIS可以通过动态规划和二分查找求解。
时间复杂度: O(nlogn)
空间复杂度: O(n)
class Solution:
def maxEnvelopes(self, envelopes: List[List[int]]) -> int:
def LIS(nums):
n = len(nums)
if n < 2: return 1
dp = [0] * n # 定义dp数组，dp[i]表示长度为i+1的LIS结尾元素的最小值
maxL = 0 # 记录LIS的长度
for num in nums:
left, right = 0, maxL
while left < right: # 二分查找num在dp数组中的插入位置
mid = left + (right - left)//2
if dp[mid] < num:
left = mid + 1
else: right = mid
dp[left] = num # 将num插入到dp数组合适的位置
if left == maxL: maxL += 1 # 如果num大于dp中所有元素，则LIS长度加1
return maxL
if not envelopes or not len(envelopes): return 0
envelopes.sort(key=lambda x: (x[0], -x[1])) # 按宽度升序和高度降序排序
weights = [i[1] for i in envelopes] # 提取排序后的信封高度数组
return LIS(weights) # 求高度数组的LIS长度作为结果返回
在解决俄罗斯套娃信封问题时，先按宽度升序排序可以确保我们在处理信封时，一定是从宽度较小的信封开始，到宽度较大的信封结束。这样可以保证宽度小的信封有可能被宽度大的信封套住。接着按高度降序排序的原因是，当宽度相同的情况下，我们只能选择最高的信封，因为较低的信封不能套在相同宽度的较高信封里。这种排序方法避免了在求最长上升子序列时将宽度相同但高度较小的信封错误地计入结果中。
不完全是这样。按高度降序排列的目的是确保在处理宽度相同的信封时，不会出现一个低的信封套在高的信封里的情况。实际上，我们在计算最长上升子序列时，仍然会考虑这些宽度相同的信封，但由于高度是降序，所以在此宽度下的信封不会形成有效的上升子序列。这确保了算法的正确性，即在宽度相同的情况下，只有最高的信封有可能被计入最终的最长套娃序列中。
在LIS函数中，dp数组的每个元素dp[i]表示长度为i+1的最长上升子序列的最小可能结尾值。这种方法有效地记录了不同长度子序列的最优结尾值，使我们能够通过比较和更新来扩展子序列。更新过程中，通过二分查找确定插入位置，能够确保每次插入操作都是优化子序列结尾值的，这样可以维护dp数组的特性，并逐步构建出整个数组的最长上升子序列。
二分查找在LIS函数中的作用是快速确定新元素应该更新dp数组中的哪个位置。通过二分查找，我们可以在对数时间复杂度内找到一个位置，使得在这个位置之前的所有元素都小于当前元素，并且这个位置的元素是大于或等于当前元素的最小值。这允许我们在保持dp数组有序的同时，有效地更新最长上升子序列的潜在结尾值，从而优化整个求解过程，使其更加高效。