You are given a 2D array of integers envelopes where envelopes[i] = [wi, hi] represents the width and the height of an envelope.
One envelope can fit into another if and only if both the width and height of one envelope are greater than the other envelope's width and height.
Return the maximum number of envelopes you can Russian doll (i.e., put one inside the other).
Note: You cannot rotate an envelope.
Solution
首先按照 \(w\) 从小到大排序，接着对于 \(h\) 则是降序排列，然后在 \(h\) 上进行 最长递增子序列 的求解即可。
点击查看代码
class Solution:
def maxEnvelopes(self, envelopes: List[List[int]]) -> int:
# sort: ascending in the x[0], descending in the x[1]
envelopes.sort(key=lambda x: (x[0], -x[1]))
top = [0 for i in range(len(envelopes))]
piles = 0
for w, h in envelopes:
left, right = 0, piles
while left < right:
mid = left + int((right-left)/2)
if top[mid] > h:
right = mid
elif top[mid] < h:
left = mid + 1
elif top[mid] == h:
right = mid
if left==piles:
piles+=1
top[left] = h
return piles