困难
给你一个二维整数数组 envelopes ，其中 envelopes[i] = [wi, hi] ，表示第 i 个信封的宽度和高度。
当另一个信封的宽度和高度都比这个信封大的时候，这个信封就可以放进另一个信封里，如同俄罗斯套娃一样。
请计算 最多能有多少个 信封能组成一组“俄罗斯套娃”信封（即可以把一个信封放到另一个信封里面）。
注意：不允许旋转信封。
前言
这道题是最长上升子序列的变种题，难点在于：首先需要先对给定的二维数组进行排序后，再求上升子序列。
题解
首先贴出经典的解法，动态规划求上升子序列。
func maxEnvelopes(envelopes [][]int) int {
n := len(envelopes)
// w升序，h降序
sort.Slice(envelopes, func(i, j int) bool {
ei, ej := envelopes[i], envelopes[j]
return ei[0] < ej[0] || (ei[0] == ej[0] && ei[1] > ej[1])
})
var dp = make([]int, n)
for i := 0; i < n; i++ {
dp[i] = 1
}
// var res int
for i := 1; i < n; i++ {
for j := 0; j < i; j++ {
if envelopes[i][1] > envelopes[j][1] {
dp[i] = max(dp[i], dp[j]+1)
}
}
// res = max(res, dp[i])
}
return max(dp...)
}
func max(a ...int) int {
res := a[0]
for _, v := range a[1:] {
if v > res {
res = v
}
}
return res
}但是很遗憾，昨天发现这个解法已经无法通过leetcode的所有测试用例了（之前是可以的），看了下官方的题解，原来是出了新的方法求上升子序列，通过二分查找的方式，时间复杂度更低。
func maxEnvelopes(envelopes [][]int) int {
//n := len(envelopes)
// w升序，h降序
sort.Slice(envelopes, func(i, j int) bool {
ei, ej := envelopes[i], envelopes[j]
return ei[0] < ej[0] || (ei[0] == ej[0] && ei[1] > ej[1])
})
var dp = make([]int, 0)
for i := range envelopes {
h := envelopes[i][1]
idx := sort.SearchInts(dp, h)
if idx < len(dp) {
dp[idx] = h
} else {
dp = append(dp, h)
}
}
return len(dp)
}题解虽然看起来更简单，其实是因为golang已经内置实现sort.SearchInts函数，通过这个函数可以找到h在上升数组dp中的index下标：
（1）如果h在dp中存在，则返回h对应的下标。
（2）如果h大于dp中最大元素，则返回下标=len(dp) （注意⚠️这个下标直接索引会越界），否则返回最小的严格大于h的元素的下标