354. 俄罗斯套娃信封问题
解法1
思路
动态规划，用A[i] 表示 [0,i]最多的信封数。
那么有初始条件 A[i]=1,
则对于数组A[i]前面的数比它小的数A[j]，有A[i] = max(A[i],A[j]+1)
所有有递推公式 A[i] = max(A[0],A[1],A[2],...A[j])+1
代码
func maxEnvelopes(envelopes [][]int) int {
if len(envelopes)==0{
return 0
}
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]
})
A := make([]int,len(envelopes))
A[0]=1
ans := 1
for i:=1;i<len(A);i++{
A[i]=1
for j:=0;j<i;j++{
if envelopes[i][0]> envelopes[j][0] && envelopes[i][1] > envelopes[j][1]{
A[i]=max(A[i],A[j]+1)
}
}
ans = max(ans,A[i])
}
fmt.Println(envelopes)
fmt.Println(A)
return ans
}
func max(a,b int)int{
if a>b{
return a
}
return b
}
时间复杂度 O(n)
解法2
思路
这个思路关键在于我们尽量维护尽可能小的数组
代码
func maxEnvelopes(envelopes [][]int) int {
if len(envelopes)==0{
return 0
}
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]
})
A := make([][]int,0,len(envelopes))
for _,item := range envelopes{
// 在数组A中寻找第一个大于item的下标,如果不存在，返回A的长度。
index := sort.Search(len(A),func(i int)bool{
return A[i][0] >= item[0] || A[i][1]>=item[1]
})
if index < len(A){
A[index]=item
}else{
A = append(A,item)
}
}
return len(A)
}
有疑问加站长微信联系（非本文作者）
