class Solution:
def bestSeqAtIndex(self, height: List[int], weight: List[int]) -> int:
hei_wei = []
for idx, hei in enumerate(height):
hei_wei.append((hei, weight[idx]))
hei_wei.sort(key=lambda x:x[0])
index_pos = collections.defaultdict(list)
index_pos[0] = [(0, 0)]
for hei, wei in hei_wei:
found = False
for key in sorted(index_pos.keys(), reverse=True):
for value in index_pos[key]:
if hei > value[0] and wei > value[1]:
# print(key)
index_pos[key+1].append((hei, wei))
found = True
break
if found:
break
return sorted(index_pos.keys(), reverse=True)[0]
进一步优化，其实默认按height顺序给weight排序，然后遍历出最深的长度
hei_wei = []
for idx, hei in enumerate(height):
hei_wei.append(weight[idx])
hei_wei.sort()
print(hei_wei)
index_pos = {}
index_pos[0] = 0
# index_pos = sorted(index_pos)
for wei in hei_wei:
for key in sorted(index_pos.keys(), reverse=True):
if wei > index_pos[key]:
if key+1 not in index_pos:
index_pos[key+1] = wei
break
print(index_pos)
return sorted(index_pos.keys(), reverse=True)[0]
然后就执行错误。猜想这个题有个巨大的坑就是相同的height可能有不同的weight。所以在按照height排序的时候，碰到相同的height的时候，weight按照降序排序，就不会把相同的height叠加到叠罗汉中
class Solution:
def bestSeqAtIndex(self, height, weight):
peoples = []
for i in range(len(height)):
peoples.append((height[i], weight[i]))
print(peoples)
# 按照height排序，相同的height，weight按照降序排序
peoples.sort(key=lambda x: [x[0], -x[1]])
# 剩下的就是在序列中找最长子序列问题
weights = [people[1] for people in peoples]
print(weights)
# index_pos = collections.defaultdict(list)
max_num = max(weights) + 1
index_pos = {}
index_pos[0] = 0
#
for weight in weights:
for key in sorted(index_pos.keys(), reverse=True):
if weight > index_pos[key]:
# print(key)
index_pos[key + 1] = min(weight, index_pos.get(key + 1, max_num))
break
#
return sorted(index_pos.keys(), reverse=True)[0]
原文：https://www.cnblogs.com/pyclq/p/14103121.html