题解 | #信封嵌套问题#

二维LIS问题

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param letters int二维数组 
# @return int
#
class Solution:
    def maxLetters(self , letters ):
        # write code here
        def LIS(nums):
            n = len(nums)
            dp = [nums[0]]

            for i in range(n):
                if dp[-1] < nums[i]:
                    dp.append(nums[i])
                else:
                    # find k in dp s.t. dp[k] < nums[i] < dp[k+1]
                    # and replace dp[k+1] with nums[i]
                    lo, hi = 0, len(dp)-2                    
                    while lo <= hi:
                        mid = lo+(hi-lo)/2
                        if dp[mid] == nums[i]:
                            break
                        elif dp[mid] < nums[i]:
                            lo = mid + 1
                        else:
                            hi = mid - 1
                    dp[lo] = nums[i]
            return len(dp)
        n = len(letters)        
        letters.sort(key=lambda x:(x[0], -x[1]))
        nums = [letters[i][1] for i in range(n)]
        return LIS(nums)