[python]:马戏团人塔

[python]:马戏团人塔

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

一、二分法
身高按升序排序，体重按降序排序。
dp数组表示一个体重递增的序列，对于当前扫描元素i来讲，如果i的体重比dp序列末尾的体重还大，那么直接放到序列的末尾（效果就是使序列变长），否则，就用元素i去替换序列中已有的元素。

class Solution:def bestSeqAtIndex(self, height: List[int], weight: List[int]) -> int:llen = len(height)person = []for i in range(llen):person.append([height[i], weight[i]])person.sort(key = lambda x:(x[0], -x[1]))dp = [0] * llenans = 0for per in person:i, j = 0, answhile i != j:mid = (i+j)//2if dp[mid] < per[1]:i = mid+1else:j = middp[i] = per[1]if i == ans:ans += 1return ans

使用二分法模块

import bisect
class Solution: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)