leetcode354 俄罗斯套娃信封问题 golang-木庄网络博客

本文摘自网络，作者，侵删。

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)
}

本文来自：简书

感谢作者：lucasgao

查看原文：leetcode354 俄罗斯套娃信封问题 golang