面试题 17.08. 马戏团人塔

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

示例：

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

Python 解答：
1.动态规划超时

class Solution:
    def bestSeqAtIndex(self, height: List[int], weight: List[int]) -> int:
        lens = len(height)
        dp = [0 for i in range(lens)]
        temp = [(height[i], weight[i]) for i in range(lens)]
        temp.sort(key=(lambda x: x[0]))
        dp[0] = 1
        for i in range(1, lens):
            select = [dp[j] for j in range(i-1, -1, -1) if temp[j][1] < temp[i][1] and temp[j][0] < temp[i][0]]
            select.append(0)
            dp[i] = max(select) + 1
        return max(dp)

2.贪心+二分法

class Solution:
    def bestSeqAtIndex(self, height: List[int], weight: List[int]) -> int:
        lens = len(height)
        dp = [0 for i in range(lens)]
        temp = [i for i in zip(height, weight)]
        temp.sort(key=(lambda x: (x[0], -x[1])))
        dp[0] = temp[0][1]
        length = 0
        for i in range(1, lens):
            if temp[i][1] > dp[length]:
                length += 1
                dp[length] = temp[i][1]
            else:
                left, right = 0, length
                while left < right:
                    mid = (left+right)//2
                    if dp[mid] >= temp[i][1]:
                        right = mid
                    elif dp[mid] < temp[i][1]:
                        left = mid+1
                dp[left] = temp[i][1]
        return length+1