354. 俄羅斯套娃信封問題

解法1

思路

動態(tài)規(guī)劃，用A[i] 表示 [0,i]最多的信封數(shù)匀们。
那么有初始條件 A[i]=1,
則對于數(shù)組A[i]前面的數(shù)比它小的數(shù)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,自己理解了 奈何表達能力有點弱 要聯(lián)系聯(lián)系了

這個思路關(guān)鍵在于我們盡量維護盡可能小的數(shù)組

也就算我們需要維護數(shù)組A冬三，數(shù)組A在迭代中滿足2個特性

1. 數(shù)組盡可能的長。
2. 在相同長度下，數(shù)字盡可能的小荒叼。

在這樣的前提下涎劈，我們求得的數(shù)組A的長度就是最長子序列的長度广凸。

證明：

1. 如果下一個數(shù)字大于數(shù)組中最大的數(shù)，那么子序列長度+1
2. 如果下一個數(shù)字p在數(shù)組中蛛枚，那我們找到數(shù)組中第一個比p大的數(shù)字q谅海，進行替換，這樣就可以保證數(shù)組的字典序盡可能小蹦浦。在這種情景下扭吁，如果下一個新來的數(shù)字x大于p小于q，那么我們就可以保證x插入到數(shù)組中，從而保證最長子序列侥袜。

數(shù)組預處理：
為了求最多的信封蝌诡，數(shù)組需要預處理。我們保證w由小到大排序系馆，h由大到小排序送漠。 h由大到小可以保證后續(xù)的數(shù)組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{
        // 在數(shù)組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)
}