俄罗斯套娃信封问题

题目描述：

给你一个二维整数数组 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 <= 5000
envelopes[i].length == 2
1 <= wi, hi <= 104

思路:

把二维排序 先固定一维，就变成了一维问题，先按第一列升序，第二列降序排序，之后就变成第二列的最大升序问题，就可以求出答案

代码:

func maxEnvelopes(envelopes [][]int) int {
    myarr:=&Intarr{envelopes,0}
    sort.Sort(myarr)
    max:=lengthOfLIS(envelopes)
    return max
}
type Intarr struct {
    marr [][]int
    line int
}
func (arr *Intarr)Len() int {
    return len(arr.marr)
}
func (arr *Intarr)Swap(i,j int)  {
    arr.marr[i],arr.marr[j]=arr.marr[j],arr.marr[i]
}
func (arr *Intarr)Less(i,j int)bool{
    if arr.marr[i][arr.line] < arr.marr[j][arr.line]{
        return  true
    }else if arr.marr[i][arr.line] > arr.marr[j][arr.line]{
        return false
    }else{
        if arr.marr[i][1]>arr.marr[j][1]{
            return true
        }else{
            return false
        }
    }
}
func lengthOfLIS(nums [][]int) int {
    if nums==nil{
        return 0
    }
    var dp [5001]int
    var max int
    for i:=0 ;i<5001;i++{
        dp[i]=1
    }
    for i:=1;i<len(nums);i++{
        max =1
        for j:=0;j<i;j++{
            if nums[i][1]>nums[j][1]{
                if max<dp[j]+1{
                    max = dp[j]+1
                }
            }
        }
        dp[i] = max
        
    }
    for i:=0;i<len(nums);i++{
        if max < dp[i]{
            max = dp[i]
        }
    }
    return max
}

代码效率：

执行用时：268 ms, 在所有 Go 提交中击败了42.09%的用户
内存消耗：6.3 MB, 在所有 Go 提交中击败了99.65%的用户