354. Russian Doll Envelopes
簡單的DP的話，會TLE芬骄，worst case O(n^2)
利用LIS這種題目的二分法的解法寒矿，真是萬萬沒想到≌玻基本想法就是把每一個新進來的元素都插入到dp中澡匪，最后計算總長度。
class Solution(object):
def maxEnvelopes(self, envelopes):
"""
:type envelopes: List[List[int]]
:rtype: int
"""
if len(envelopes) <= 1:
return len(envelopes)
envs = sorted(envelopes, key=lambda x: (x[0], -x[1]))
dp = [0]*len(envs)
l = 0
for e in envs:
index = self.search(dp, 0, l, e[1])
dp[index] = e[1]
if index == l:
l += 1
return l
def search(self, dp, start, end, target):
# find the most left index to insert target
while start + 1 < end:
mid = (start + end) / 2
if dp[mid] < target:
start = mid
else:
end = mid
if dp[start] >= target:
return start
else:
return end
