面试题 17.08. 马戏团人塔(最长上升子序列)

相当于求一个二维的最长下降子序列，这里为了符合习惯，求上升序列
对于一维的最长上升子序列，有o(n²)的dp解法（本题会超时），更优的是利用二分实现o(n*logn)的时间复杂度
在dp解法中dp[n]表示的是包含第n个数在内的前n个数所组成的最长上升子序列的长度
而二分中，dp[n]表示存在长度为n的上升子序列中的最大值
对于一个子序列，我们希望其最大值越小越好，因为越小后面的值就越容易接上，每当要插入一个数时，利用二分法查找可以插入的位置，如果出现了更大的n就更新答案。
例如，对于子序列1，2，5，8，10其dp数组为dp[0] = 1,dp[1] = 2…dp[4] = 10，
此时如果插入 6，二分定位得到在大于dp[2]，小于dp[3]处，即6可以接在长度为3并且末尾为5的子序列后面形成更长的长度为4的子序列，所以需要更新dp[3]的值，因为在同样长度下以6为末尾显然比以8为末尾更优。
如果插入12，则定位在大于dp[4]，即大于当前最长的子序列的最大值，显然出现了更长的上升子序列，所以令dp[5]=12，同时更新最大长度

对于本题来说，当我们对体重或者身高任意一维排序后，问题就化为了求最长上升子序列的问题
本题要求上面的人的体重和身高是严格小于下面的人的，所以当我们对身高排序后，针对身高相同的人只能有一个的这一限制，我们将身高相同的人按照体重降序排列，因为接下来要求的是上升子序列，所以对其降序排列后，身高一样的人最多只会出现一个（出现两个及以上就不符合升序的要求了）

class Solution {
    public int bestSeqAtIndex(int[] height, int[] weight) {
        int[][] a = new int[height.length][2];
        for(int i = 0; i < height.length; i++){
            a[i][0] = height[i];
            a[i][1] = weight[i];
        }
        Arrays.sort(a,(o1,o2) -> o1[0] == o2[0]?o2[1] - o1[1]:o1[0] - o2[0]);
        int[] dp = new int[height.length];
        int ans = 0;
        for(int i = 0; i < height.length; i++){
            //dp[i] = 1;
            //for(int j = 0; j < i; j++){
            //    if(a[i][1] > a[j][1] && a[i][0] > a[j][0]){
            //        dp[i] = Math.max(dp[i],dp[j] + 1);
            //    }
            //}
            //ans = Math.max(dp[i],ans);
            int l = 0, r = ans;
            while(l < r){
                int mid = (l + r) >> 1;
                if(a[i][1] > dp[mid]){
                    l = mid + 1;
                }else{
                    r = mid;
                }
            }
            dp[l] = a[i][1];
            if(ans == l)
                ans++;
        }
        return ans;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34