马戏团人塔

有个马戏团正在设计叠罗汉的表演节目，一个人要站在另一人的肩膀上。出于实际和美观的考虑，在上面的人要比下面的人矮一点且轻一点。已知马戏团每个人的身高和体重，请编写代码计算叠罗汉最多能叠几个人。

示例：

输入：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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/circus-tower-lcci
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

public int bestSeqAtIndex(int[] height, int[] weight) {
    int len = height.length;
    int[][] array = new int[len][2];
    for(int i = 0;i<len;i++){
        array[i][0] = height[i];
        array[i][1] = weight[i];
    }
    Arrays.sort(array,(a, b)->a[0]==b[0]?b[1]-a[1]:a[0]-b[0]);
    int[] dp = new int[len];
    int res = 0;
    for(int[] arr: array){
        int i = 0, j = res;
        while(i<j){
            int middle = (i+j)/2;
            if(dp[middle]<arr[1])
                i = middle+1;
            else
                j = middle;
        }
        dp[i] = arr[1];
        if(j==res) res++;
    }
    return res;
}

作者：Pathwax
链接：https://leetcode-cn.com/problems/circus-tower-lcci/solution/java-by-pathwax-zwcj/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

class Solution {
    public int bestSeqAtIndex(int[] height, int[] weight) {
        int len = height.length;
        int[][] person = new int[len][2];
        for (int i = 0; i < len; ++i){
            person[i] = new int[]{height[i], weight[i]};
        }
            
        //根据身高排序，身高相同根据体重排序
        Arrays.sort(person, (a, b) -> a[0] == b[0] ? b[1] - a[1] : a[0] - b[0]);
        int[] dp = new int[len];
        int res = 0;
        for (int[] pair : person) {
            int i = Arrays.binarySearch(dp, 0, res, pair[1]);
            //Arrays.binarySearch(object[], int fromIndex, int endIndex, object key);
            //从0到res查找体重为pair[1]的下标
            //查到目标元素时，返回目标的index
            //查不到目标元素时，返回（最后一个查找的元素的index+1）
            if (i < 0) i = -(i + 1);
            dp[i] = pair[1];
            if (i == res)++res;//到达右边界，右边界向后移动1
        }
        return res;
    }
}

作者：gfu
链接：https://leetcode-cn.com/problems/circus-tower-lcci/solution/xian-gen-ju-shen-gao-pai-xu-ruo-shen-gao-yi-yang-z/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

Arrays.binarySearch(object[], int fromIndex, int endIndex, object key);理解例子

import java.util.Arrays;
public class IntFunction
{
    public static void main (String []args)
    {
        int a[] = new int[] {1, 3, 4, 6, 8, 9};
        int x1 = Arrays.binarySearch(a, 5);
        int x2 = Arrays.binarySearch(a, 4);
        int x3 = Arrays.binarySearch(a, 0);
        int x4 = Arrays.binarySearch(a, 10);
        System.out.println("x1:" + x1 + ", x2:" + x2);
        System.out.println("x3:" + x3 + ", x4:" + x4);
    }
}
/*输出结果：
x1:-4, x2:2
x3:-1, x4:-7
*/

赏

谢谢你请我吃糖果

微信