IOS 算法(困难篇) ----- 俄罗斯套娃信封问题

给你一个二维整数数组 envelopes ，其中 envelopes[i] = [wi, hi] ，表示第 i 个信封的宽度和高度。当另一个信封的宽度和高度都比这个信封大的时候，这个信封就可以放进另一个信封里，如同俄罗斯套娃一样。
请计算 最多能有多少个 信封能组成一组“俄罗斯套娃”信封（即可以把一个信封放到另一个信封里面）。
注意：不允许旋转信封。

例子

输入：envelopes = [[5,4],[6,4],[6,7],[2,3]]
输出：3
解释：最多信封的个数为 3, 组合为: [2,3] => [5,4] => [6,7]。

输入：envelopes = [[1,1],[1,1],[1,1]]
输出：1

解题思路

题意好理解, 不过这道题一共2个难点需要重点处理下

1.排序
2.排序之后的查找

首先 第一维度(下标为0元素组成的数组)正序排列便于处理, 这个是大家肯定会想到的处理方式,
那么我们重点看下第二维度(下标为1元素组成的数组)怎么处理

例子:

[[2, 3], [4, 5], [6, 6], [6, 7]]

第一维度 [2, 4, 6, 6] (下标为0元素组成的数组)
第二维度 [3, 5, 6, 7] (下标为1元素组成的数组)

结果3, 没问题, 看第一维度就可以得出,

但是先不看第一维度, 我们看第二维度呢 [3, 5, 6, 7] 应该是4啊

那么我们再看下这个

[[2, 3], [4, 5], [6, 7], [6, 6]]

第二维度 [2, 4, 6, 6]
第二维度 [3, 5, 7, 6]

这样看第二维度 [3, 4, 7, 6], 最长递增子序列的长度是 3 即正确结果

所以，利用这个特性 第一个维度递增，如果第一维度相等,第二个维度递减的顺序 进行排序处理,
然后找第二维度最长递增子序列即可

这里我建议先做下IOS 算法(中级篇) ----- 最长递增子序列 , 后面找最大就比较好理解了

未翻译版

    func maxEnvelopes(_ envelopes: [[Int]]) -> Int {

        if envelopes.count == 0 { return 0 }
        
        var temp = envelopes
        temp = temp.sorted { (a, b) -> Bool in
            if a[0] == b[0]{
                return a[1] > b[1]
            } 
            return a[0] < b[0]
        }
        
        var f = Array.init(repeating: 1, count: temp.count)
        for i in 0..<temp.count  {
            for j in 0..<i {
                if(temp[i][1] > temp[j][1]) {
                    f[i] = max(f[i], f[j]+1)
                }
            }
        }
        return f.max() ?? 1
}

翻译版

    func maxEnvelopes(_ envelopes: [[Int]]) -> Int {

        // 空数组直接返回
        if envelopes.count == 0 { return 0 }
        
        // 定义一个容器数组为原数组
        var temp = envelopes

        // 容器数组按上述方法排序
        temp = temp.sorted { (a, b) -> Bool in
            
            // 第一维度相等, 则第二维度倒序排列
            if a[0] == b[0]{
                return a[1] > b[1]
            } 
            // 第一维度正序排列
            return a[0] < b[0]
        }

        // 接下来就变成了找第二维度最长递增子序列
        var f = Array.init(repeating: 1, count: temp.count)

        // 动态规划求解找到最长子序列
        for i in 0..<temp.count  {
            for j in 0..<i {
                if(temp[i][1] > temp[j][1]) {
                    f[i] = max(f[i], f[j]+1)
                }
            }
        }
        // 返回结果
        return f.max() ?? 1
}

题目来源：力扣（LeetCode） 感谢力扣爸爸 :)
IOS 算法合集地址