gold-17-8

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

示例：

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

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][0] = height[i];
            person[i][1] = weight[i];
        }
        //身高升序排列，体重降序排列，保证升高相同的人只有一个被选中，转化为求体重的最长递增序列（LIS）
        Arrays.sort(person,(a,b) -> a[0] == b[0] ? b[1] - a[1] : a[0] - b[0]);
        int[] arr = new int[len];//arr存储长度为i + 1的LIS的最小末尾
        //初始化，长度为1的最长递增序列的最小末尾为person[0][1](实际上是体重的最小值，后续通过遍历person[i][1]更新)
        arr[0] = person[0][1];
        int cur = 1;//cur记录当前递增序列的最大长度
        //遍历记录体重的数组person[i][1]，更新arr;
        for (int i = 1; i < len; i++) {
            int next = person[i][1];
            //下一个体重值比arr中记录的所有值大，即出现长度更长(为cur+1)的LIS，在arr中记录此长度序列的最后一个值
            if (next > arr[cur - 1]){
                arr[cur++] = next;
            }else {
                //出现末尾更小的LIS，通过二分查找在arr中查找对应序列长度的下标，更新arr中记录的最小末尾
                int index = binarySearch(arr,cur,next);
                arr[index] = next;
            }
        }
        return cur;
    }

    // 二分查找变体 找到第一个大于等于target的位置index
    private int binarySearch(int[] arr, int cur, int target) {
        int left = 0, right = cur - 1;
        while (left < right){
            int mid = left + ((right - left) >> 1);
            if (arr[mid] < target){
                left = mid + 1;
            }else {
                right = mid;
            }
        }
        return left;
    }
}