马戏团人塔

难度: Medium

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

示例：

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

Submission

运行时间: 146 ms

内存: 18.4 MB

class Solution:
	def bestSeqAtIndex(self, height: List[int], weight: List[int]) -> int:
		order_number=0
		order_height = sorted(range(len(height)),key= lambda d:(height[d],-weight[d]))
		d_tail=[weight[order_height[0]]]
		for i in range(1,len(order_height)):
			get_num = weight[order_height[i]]
			if d_tail[-1] < get_num:
				d_tail.append(get_num)
			else:
				pos = bisect.bisect_right(d_tail,get_num)
				if d_tail[pos-1]!=get_num:
					d_tail[pos] = get_num
				'''
				left,right = 0,(len(d_tail) - 1)
				while left < right:
					mid = (left + right) >> 1
					if d_tail[mid] < get_num:
						left = mid + 1
					else:
						right=mid
				d_tail[left] = get_num
				'''
		return len(d_tail)

Explain

首先，对输入的身高和体重进行处理，按身高升序、体重降序的方式进行排序，这样可以确保在相同身高的情况下，体重较重的人排在前面。然后，使用一个动态数组 d_tail 来记录当前可以叠罗汉的最长序列，初始时只包含第一个人的体重。接着，遍历排序后的每个人，对于每个人，检查他们的体重是否可以放在当前的叠罗汉序列的末尾，如果可以，则将他们的体重添加到序列末尾；否则，使用二分查找在序列中找到一个位置，使得该位置之前的所有人的体重都小于当前人的体重，并将当前人的体重放在这个位置。最后，返回 d_tail 的长度，即为最多能叠的人数。

时间复杂度: O(n log n)

空间复杂度: O(n)

class Solution:
    def bestSeqAtIndex(self, height: List[int], weight: List[int]) -> int:
        order_number=0
        order_height = sorted(range(len(height)),key= lambda d:(height[d],-weight[d]))
        d_tail=[weight[order_height[0]]]
        for i in range(1,len(order_height)):
            get_num = weight[order_height[i]]
            if d_tail[-1] < get_num:
                d_tail.append(get_num)
            else:
                pos = bisect.bisect_right(d_tail,get_num)
                if d_tail[pos-1]!=get_num:
                    d_tail[pos] = get_num
        return len(d_tail)

Explore

这种排序策略是为了简化问题。首先按身高升序排列确保在处理体重时，只需要考虑身高相同或更高的人。如果身高相同，再按体重降序排列可以确保在同一身高内，体重较重的人排在前面，这样当我们构建基于体重的最长递增子序列时，可以避免身高相同但体重较轻的人被错误地叠加到身高相同但体重较重的人上面。这样，我们只需关注体重的单调性，而不需要担心身高对叠罗汉顺序的影响。

在这个问题中，动态数组 d_tail 的每个元素代表在当前考虑的人员中，能够组成的最长递增子序列的体重值。数组的长度表示最长递增子序列的长度，而每个位置上的体重值表示在构建这个序列时，每个阶段可容纳的最小体重。这样，d_tail 数组不仅记录了最长序列的长度，还通过每个位置的体重值，保证了序列的最优性（即尽可能让序列中的体重值较小，这样有利于后续更大的体重值加入到序列中）。

当新加入的人的体重大于 d_tail 数组的最后一个元素时，这表示当前考虑的这个人可以放在已有的最长递增子序列之后，形成一个更长的递增序列。由于 d_tail 数组维护的是一个体重递增的序列，新加入的体重更大，直接添加到末尾可以延长这个序列而不破坏其递增的性质。这反映了动态规划中逐步构建解决方案的思想，即利用已有的最优解构建新的更优解。