问题描述
You are given a 2D array of integers envelopes where envelopes[i] = [wi, hi] represents the width and the height of an envelope.
One envelope can fit into another if and only if both the width and height of one envelope are greater than the other envelope’s width and height.
Return the maximum number of envelopes you can Russian doll (i.e., put one inside the other).
Note: You cannot rotate an envelope.
Example 1:
Input: envelopes = [5,4],[6,4],[6,7],[2,3]
Output: 3
Explanation: The maximum number of envelopes you can Russian doll is 3 ([2,3] => [5,4] => [6,7]).
Example 2:
Input: envelopes = [1,1],[1,1],[1,1]
Output: 1
Constraints:
- 1 <= envelopes.length <= 5000
- envelopes[i].length == 2
- 1 <= wi, hi <= 10^4
问题分析
题目要求信封不允许旋转，因此套娃可能的条件必须为宽高均小于另外一个信封。
这里初步的想法是：假设初始只有一个宽度最大的信封X，那么最大套娃数量明显是1；此时来了一个宽第二大的信封A，如果A能够放进X，则最大套娃数量为2；否则仍为1；如果这时候再来一个信封B，那么有2种情况：
- B能放进X, 此时最大套娃数量为2
- B能放进A, 此时最大套娃数量为在A的基础上+1
那么以此类推，我们可以得知所有信封添加完后，过程中的最大套娃数量即为所求。
这里要按照宽度倒序处理的原因是：降低比较次数；如果是乱序的，我们需要尝试各种顺序才能避免遗漏；
初始解法
func maxEnvelopes(envelopes [][]int) int {
ans := 1
// first sort by width
sort.Slice(envelopes, func(i, j int) bool {
return envelopes[i][0] < envelopes[j][0]
})
length := len(envelopes)
m := make([]int, length)
m[length-1] = 1
for i := length - 2; i >= 0; i-- {
max := 0
for j := i + 1; j < length; j++ {
if envelopes[i][0] < envelopes[j][0] && envelopes[i][1] < envelopes[j][1] {
if m[j] > max {
max = m[j]
}
}
}
m[i] = max + 1
if m[i] > ans {
ans = m[i]
}
}
return ans
}
优化解法
初始解法的时间复杂度为O(N^2)。
提交AC后，在讨论区看到，本道题还有一种优化到O(NlogN)的解法，其本质和求最大递增子序列(LIS)问题类似。
大概步骤为：维护一个dp数组，对于A[i]，找到A[i]在dp中的lower_bound，即不小于A[i]的第一个数的位置。如果找到了，则将dp中该元素替换为A[i]；如果未找到，说明dp数组中每一个元素都小于A[i]，此时将A[i]添加到dp数组末尾即可。在查找lower_bound的过程中使用二分查找降低查找次数
回到本题，这里需要对信封数组进行排序，依然是按照宽度升序排列；但是如果宽度一致，则按照高度降序排列。这么排序的原因是：按照宽升序排列后，依次遍历时，如果不存在相同宽的情况，那么实际我们只需考虑高度即可。如果存在高度相同的情况，当我们按照高度降序排列后，在执行LIS算法过程中，对于A[i]>=A[i+1]，那么A[i]是A[i+1]的lower_bound，因此会被A[i+1]替换掉；那么对于M个宽度相同，高度降序排列的信封来说，实际最后保留的仅是最后一个高度最低的，也就不会出现相同宽度信封套娃的情况。
在优化解法中，我们维护一个结果数组res, 用来存储套娃信封的高度，然后对于每一个信封高度，在res中进行二分查找它的lower_bound。找到了就用当前元素替换，找不到就直接append，最后res的长度即为所求。
这里二分查找的过程中，有个小技巧：r初始化为len(res)，而不是传统二分查找做法里的len(res)-1。这么做是因为我们要找的是lower_bound，而不是精确的查找某个值，所以我们用右边界去逼近目标值。如果查找完，右边界没有向左移动，说明没有找到，此时我们判断如果r == len(res)，直接进行append操作即可。
func maxEnvelopesV2(envelopes [][]int) int {
// first sort asc by width, desc by height
sort.Slice(envelopes, func(i, j int) bool {
if envelopes[i][0] == envelopes[j][0] {
return envelopes[i][1] > envelopes[j][1]
}
return envelopes[i][0] < envelopes[j][0]
})
res := []int{envelopes[0][1]}
for i := 1; i < len(envelopes); i++ {
// find lower_bound of envelopes[i][1]
l, r := 0, len(res)
for {
if l >= r {
break
}
mid := l + (r-l)/2
if res[mid] < envelopes[i][1] {
l = mid + 1
} else {
r = mid
}
}
// not found, means all elements in res are smaller than target
if r == len(res) {
res = append(res, envelopes[i][1])
} else {
// else just replace the lower_bound
res[r] = envelopes[i][1]
}
}
return len(res)
}