二分法 馬戲團疊羅漢

題目

有個馬戲團正在設(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)

提示：

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] = 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]);
            if (i < 0)
                i = -(i + 1);
            dp[i] = pair[1];
            if (i == res)
                ++res;
        }
        return res;
    }
}