yankewei
commented
3 years ago 动态规划
func maxEnvelopes(envelopes [][]int) int {
var ret int
sort.Slice(envelopes, func (i, j int) bool {
a, b := envelopes[i], envelopes[j]
return a[0] < b[0] || (a[0] == b[0] && a[1] < b[1])
})
s := make([]int, len(envelopes))
for i := 0; i < len(envelopes); i++ {
s[i] = 1
for j := 0; j < i; j++ {
a, b := envelopes[i], envelopes[j]
if a[0] > b[0] && a[1] > b[1] {
s[i] = max(s[i], s[j] + 1)
}
}
ret = max(ret, s[i])
}
return ret
}
func max(x, y int) int {
if x > y {
return x
}
return y
}二分查找
func maxEnvelopes(envelopes [][]int) int {
sort.Slice(envelopes, func(i, j int) bool {
a, b := envelopes[i], envelopes[j]
return a[0] < b[0] || a[0] == b[0] && a[1] > b[1]
})
f := []int{}
for _, e := range envelopes {
h := e[1]
if i := sort.SearchInts(f, h); i < len(f) {
f[i] = h
} else {
f = append(f, h)
}
}
return len(f)
}
给你一个二维整数数组 envelopes ，其中 envelopes[i] = [wi, hi] ，表示第 i 个信封的宽度和高度。
当另一个信封的宽度和高度都比这个信封大的时候，这个信封就可以放进另一个信封里，如同俄罗斯套娃一样。
请计算 最多能有多少个 信封能组成一组“俄罗斯套娃”信封（即可以把一个信封放到另一个信封里面）。
注意：不允许旋转信封。
示例 1：
示例 2：
提示：
来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/russian-doll-envelopes 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。