354. 俄羅斯套娃信封問題

困難

給你一個二維整數(shù)數(shù)組?envelopes?，其中?envelopes[i] = [wi, hi]?，表示第?i?個信封的寬度和高度。

當(dāng)另一個信封的寬度和高度都比這個信封大的時候，這個信封就可以放進(jìn)另一個信封里，如同俄羅斯套娃一樣。

請計算?最多能有多少個?信封能組成一組“俄羅斯套娃”信封（即可以把一個信封放到另一個信封里面）。

注意：不允許旋轉(zhuǎn)信封。

前言

這道題是最長上升子序列的變種題，難點(diǎn)在于：首先需要先對給定的二維數(shù)組進(jìn)行排序后，再求上升子序列。

題解

首先貼出經(jīng)典的解法，動態(tài)規(guī)劃求上升子序列。

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
}

但是很遺憾，昨天發(fā)現(xiàn)這個解法已經(jīng)無法通過leetcode的所有測試用例了（之前是可以的），看了下官方的題解，原來是出了新的方法求上升子序列，通過二分查找的方式，時間復(fù)雜度更低。

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

題解雖然看起來更簡單，其實(shí)是因?yàn)間olang已經(jīng)內(nèi)置實(shí)現(xiàn)sort.SearchInts函數(shù)，通過這個函數(shù)可以找到h在上升數(shù)組dp中的index下標(biāo)：

（1）如果h在dp中存在，則返回h對應(yīng)的下標(biāo)。

（2）如果h大于dp中最大元素，則返回下標(biāo)=len(dp) （注意??這個下標(biāo)直接索引會越界），否則返回最小的嚴(yán)格大于h的元素的下標(biāo)文章來源地址http://www.zghlxwxcb.cn/news/detail-849076.html

到了這里，關(guān)于動態(tài)規(guī)劃算法 - LC354. 俄羅斯套娃信封問題的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！