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

思路

2021年03月04日 v1,自己理解了 奈何表达能力有点弱 要联系联系了

这个思路关键在于我们尽量维护尽可能小的数组

也就算我们需要维护数组A，数组A在迭代中满足2个特性

1. 数组尽可能的长。
2. 在相同长度下，数字尽可能的小。

在这样的前提下，我们求得的数组A的长度就是最长子序列的长度。

证明：

1. 如果下一个数字大于数组中最大的数，那么子序列长度+1
2. 如果下一个数字p在数组中，那我们找到数组中第一个比p大的数字q，进行替换，这样就可以保证数组的字典序尽可能小。在这种情景下，如果下一个新来的数字x大于p小于q，那么我们就可以保证x插入到数组中，从而保证最长子序列。

数组预处理：
为了求最多的信封，数组需要预处理。我们保证w由小到大排序，h由大到小排序。 h由大到小可以保证后续的数组A字典序尽可能小

代码

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