有個馬戲團正在設計疊羅漢的表演節目,一個人要站在另一人的肩膀上。出于實際和美觀的考慮,在上面的人要比下面的人矮一點且輕一點。已知馬戲團每個人的身高和體重,請編寫代碼計算疊羅漢最多能疊幾個人。
示例:
輸入: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)
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;//在已經選擇了的體重中,找出當前體重應該放置的位置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;}
}