[Python手撕]马戏团人塔

class Solution:
    def bestSeqAtIndex(self, height: List[int], weight: List[int]) -> int:


        n = len(height)
        persons = [[height[i],weight[i]] for i in range(n)]

        persons.sort(key=lambda x: x[0])

        n = len(persons)
        dp = [1] * n

        for i in range(n):
            for j in range(i):
                if persons[i][0] > persons[j][0] and persons[i][1] > persons[j][1]:
                    dp[i] = max(dp[i], dp[j] + 1)

        return max(dp)

class Solution:
    def bestSeqAtIndex(self, height: List[int], weight: List[int]) -> int:

        n = len(height)
        people = [[height[i], weight[i]] for i in range(n)]
        people.sort(key=lambda x: (x[0],-x[1]))

        # 用于存储体重的LIS
        lis = []

        for _, weight in people:
            pos = bisect_left(lis, weight)
            # 如果pos等于lis的长度，说明weight比lis中所有元素都大，可以加入
            if pos == len(lis):
                lis.append(weight)
            else:
                # 否则更新lis中位置pos的值
                lis[pos] = weight

        return len(lis)