python3 解法, 执行用时: 216 ms, 内存消耗: 18.2 MB, 提交时间: 2023-04-22 12:04:16

class Solution:
    import bisect
    def bestSeqAtIndex(self, height: List[int], weight: List[int]) -> int:       
       dp=[]
       for a,b in sorted(zip(height,weight),key = lambda x:[x[0],-x[1]]):
           pos = bisect.bisect_left(dp,b)
           dp[pos:pos+1] = [b]
       return len(dp)

python3 解法, 执行用时: 364 ms, 内存消耗: 18.6 MB, 提交时间: 2023-04-22 12:03:56

'''
先按照身高升序，体重降序排序将问题从二维问题变为一维问题
然后问题就变成为在一堆体重序列中查找【最长递增子序列】的问题，
然后此时可以使用【动态规划】解决问题，但是在这道题用动态规划会超时，
所以改用【贪心+二分查找】的方法，不懂的小伙伴可以查看leetcode 300题【最长递增子序列】
'''
class Solution:
    def bestSeqAtIndex(self, height: List[int], weight: List[int]) -> int:
        newList = list()
        for i in range(len(height)):
            newList.append([height[i], weight[i]])
        newList.sort(key=lambda x:[x[0], -x[1]])
        dp = list()
        for i in range(len(newList)):
            if not dp or newList[i][1] > dp[-1][1]:
                dp.append(newList[i])
            else:
                l = 0
                r = len(dp) - 1
                while l < r:
                    mid = (r + l) // 2
                    if newList[i][1] <= dp[mid][1]:
                        r = mid
                    else:
                        l = mid + 1
                dp[l] = newList[i]
        return len(dp)

cpp 解法, 执行用时: 108 ms, 内存消耗: 47.5 MB, 提交时间: 2023-04-22 12:03:09

/*
先排序：高度升序排列，相同高度的宽度降序排列
然后DP数组下标 i 位置记录长为 i+1 最长递增序列末尾数字最小值
最后返回DP数组长度
PS（新瓶装旧酒，和 俄罗斯套娃信封 问题一样）
*/
class Solution {
public:
    int bestSeqAtIndex(vector<int>& height, vector<int>& weight) {
        vector<pair<int,int>> tmp;
        for(int i = 0; i < height.size(); i++) tmp.push_back({height[i], weight[i]});
        sort(tmp.begin(), tmp.end(), [](const pair<int,int> &a, const pair<int,int> &b) {
            return a.first == b.first ? a.second > b.second : a.first < b.first;
        });
        vector<int> dp; //长度为N的地方 最小的数字
        for(const auto &[h, w]: tmp) {
            auto p = lower_bound(dp.begin(), dp.end(), w);  //二分查找第一个大于等于的地方
            if(p == dp.end()) dp.push_back(w);
            else *p = w;
        }
        return dp.size();
    }
};

java 解法, 执行用时: 67 ms, 内存消耗: 43.4 MB, 提交时间: 2023-04-22 12:02:32

class Solution {
    public int bestSeqAtIndex(int[] height, int[] weight) {
        int len = height.length;
        int[][] arr = new int[len][2];
        for(int i = 0; i < len; i++){
            arr[i][0] = height[i];
            arr[i][1] = weight[i];
        }

        Arrays.sort(arr, (o1, o2) -> {
            if(o1[0] == o2[0]){
                return Integer.compare(o1[1], o2[1]);
            }
            return Integer.compare(o2[0], o1[0]);
        });

        // System.out.println(Arrays.deepToString(arr));
        int[][] dp = new int[len + 1][2];
        dp[1] = arr[0];
        int index = 1;
        for(int i = 1; i < len; i++){
            if(arr[i][1] < dp[index][1]){
                dp[++index] = arr[i];
            } else {
                int pos = find(dp, arr[i], index);
                dp[pos] = arr[i];
            }
        }

        return index;
    }

    public int find(int[][] dp, int[] person, int index){
        int left = 1;
        int right = index;
        while(left < right){
            int mid = (left + right) / 2;
            if(dp[mid][1] <= person[1]){
                right = mid; 
            } else {
                left = mid + 1;
            }
        }

        return right;
    }
}

java 解法, 执行用时: 54 ms, 内存消耗: 43.2 MB, 提交时间: 2023-04-22 12:01:52

// 二分查找法
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;
    }
}