给你一个二维整数数组 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 算法合集地址
网友评论