354. 俄罗斯套娃信封问题
困难
给你一个二维整数数组 envelopes
,其中 envelopes[i] = [wi, hi]
,表示第 i
个信封的宽度和高度。
当另一个信封的宽度和高度都比这个信封大的时候,这个信封就可以放进另一个信封里,如同俄罗斯套娃一样。
请计算 最多能有多少个 信封能组成一组“俄罗斯套娃”信封(即可以把一个信封放到另一个信封里面)。
注意:不允许旋转信封。
前言
这道题是最长上升子序列的变种题,难点在于:首先需要先对给定的二维数组进行排序后,再求上升子序列。
题解
首先贴出经典的解法,动态规划求上升子序列。
func maxEnvelopes(envelopes [][]int) int {
n := len(envelopes)
// w升序,h降序
sort.Slice(envelopes, func(i, j int) bool {
ei, ej := envelopes[i], envelopes[j]
return ei[0] < ej[0] || (ei[0] == ej[0] && ei[1] > ej[1])
})
var dp = make([]int, n)
for i := 0; i < n; i++ {
dp[i] = 1
}
// var res int
for i := 1; i < n; i++ {
for j := 0; j < i; j++ {
if envelopes[i][1] > envelopes[j][1] {
dp[i] = max(dp[i], dp[j]+1)
}
}
// res = max(res, dp[i])
}
return max(dp...)
}
func max(a ...int) int {
res := a[0]
for _, v := range a[1:] {
if v > res {
res = v
}
}
return res
}
但是很遗憾,昨天发现这个解法已经无法通过leetcode的所有测试用例了(之前是可以的),看了下官方的题解,原来是出了新的方法求上升子序列,通过二分查找的方式,时间复杂度更低。
func maxEnvelopes(envelopes [][]int) int {
//n := len(envelopes)
// w升序,h降序
sort.Slice(envelopes, func(i, j int) bool {
ei, ej := envelopes[i], envelopes[j]
return ei[0] < ej[0] || (ei[0] == ej[0] && ei[1] > ej[1])
})
var dp = make([]int, 0)
for i := range envelopes {
h := envelopes[i][1]
idx := sort.SearchInts(dp, h)
if idx < len(dp) {
dp[idx] = h
} else {
dp = append(dp, h)
}
}
return len(dp)
}
题解虽然看起来更简单,其实是因为golang已经内置实现sort.SearchInts函数,通过这个函数可以找到h在上升数组dp中的index下标:
(1)如果h在dp中存在,则返回h对应的下标。文章来源:https://www.toymoban.com/news/detail-849076.html
(2)如果h大于dp中最大元素,则返回下标=len(dp) (注意⚠️这个下标直接索引会越界),否则返回最小的严格大于h的元素的下标文章来源地址https://www.toymoban.com/news/detail-849076.html
到了这里,关于动态规划算法 - LC354. 俄罗斯套娃信封问题的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!