有個馬戲團正在設(shè)計疊羅漢的表演節(jié)目，一個人要站在另一人的肩膀上。出于實際和美觀的考慮，在上面的人要比下面的人矮一點且輕一點。已知馬戲團每個人的身高和體重，請編寫代碼計算疊羅漢最多能疊幾個人。

示例：

輸入：height = [65,70,56,75,60,68] weight = [100,150,90,190,95,110]
輸出：6
解釋：從上往下數(shù)，疊羅漢最多能疊 6 層：(56,90), (60,95), (65,100), (68,110), (70,150), (75,190)

class Solution {int[] dp;public int bestSeqAtIndex(int[] height, int[] weight) {int n=height.length;int[][] com=new int[n][2];for(int c=0;c<n;c++){com[c][0]=height[c];com[c][1]=weight[c];}Arrays.sort(com,(o1, o2) -> o1[0]==o2[0]?o2[1]-o1[1]:o1[0]-o2[0]);//身高升序，體重降序dp=new int[n];int res=0;dp[res]=com[0][1];res++;for(int i=1;i<n;i++)if(com[i][1]>dp[res-1]) dp[res++]=com[i][1];else {int l=0,r=res-1;//在已經(jīng)選擇了的體重中，找出當(dāng)前體重應(yīng)該放置的位置while (l<=r){int mid=(r-l)/2+l;if(dp[mid]>=com[i][1])r=mid-1;else l=mid+1;}dp[l]=com[i][1];}return res;} }

總結(jié)

以上是生活随笔為你收集整理的leetcode面试题 17.08. 马戏团人塔（二分法）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。