本篇內容主要講解“leetcode怎么解決馬戲團人塔問題”，感興趣的朋友不妨來看看。本文介紹的方法操作簡單快捷，實用性強。下面就讓小編來帶大家學習“leetcode怎么解決馬戲團人塔問題”吧!
有個馬戲團正在設計疊羅漢的表演節目，一個人要站在另一人的肩膀上。出于實際和美觀的考慮，在上面的人要比下面的人矮一點且輕一點。已知馬戲團每個人的身高和體重，請編寫代碼計算疊羅漢最多能疊幾個人。
示例：
輸入：height = [65,70,56,75,60,68] weight = [100,150,90,190,95,110]
輸出：6
解釋：從上往下數，疊羅漢最多能疊 6 層：(56,90), (60,95), (65,100), (68,110), (70,150), (75,190)提示：
height.length == weight.length <= 10000
解題思路
1，先按照身高升序排序
2，相同身高，按照體重降序排序
3，身高轉化成了最長遞增序列問題
代碼實現
func bestSeqAtIndex(height []int, weight []int) int {if len(weight)<1{return 0}for i:=0;i<len(height);i++{for j:=i;j<len(height);j++{if height[i]>height[j]{height[i],height[j]=height[j],height[i]weight[i],weight[j]=weight[j],weight[i]}}}for i:=0;i<len(weight)-1;i++{j:=1for i+j<len(weight) && height[i]==height[i+j]{j++}weight=sort(weight,i,j)i+=j}var dp []intdp=append(dp,weight[0])for i:=1;i<len(weight);i++{if weight[i]>dp[len(dp)-1]{dp=append(dp,weight[i])}else{l:=0r:=len(dp)-1p:=0for l<=r{mid:=(l+r)>>1if weight[i]>dp[mid]{p=mid+1l=mid+1}else{r=mid-1}}dp[p]=weight[i]}}fmt.Println(dp)return len(dp)}func sort(a []int,s,e int)[]int{for i:=s;i<=e;i++{for j:=i;j<e;j++{if a[i]<a[j]{a[i],a[j]=a[j],a[i]}}}return a}
到此，相信大家對“leetcode怎么解決馬戲團人塔問題”有了更深的了解，不妨來實際操作一番吧！這里是億速云網站，更多相關內容可以進入相關頻道進行查詢，關注我們，繼續學習！
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
