边工作边刷题：70天一遍leetcode: day 41

Russian Doll Envelopes

要点：题目实际不是难题，就是排序+longest increasing subsequence。

• 有一点需要注意，因为width相等的情况是不能二者同时考虑的。简单的技巧是对width相等时height大的在前，这样在做LIS的时候不可能二者同时被选。
• O(n^2)计算LIS会TLE，nlgn的方法是抄的。

class Solution(object):
    def maxEnvelopes(self, envelopes):
        """
        :type envelopes: List[List[int]]
        :rtype: int
        """
        def lis(nums):
            n = len(nums)
            dp = [0]*(n+1)
            for i in xrange(1, n+1):
                for j in xrange(i):
                    if j==0 or nums[i-1]>nums[j-1]:
                        dp[i]=max(dp[i], dp[j]+1)
            
            return max(dp)

        def lis_nlgn(nums):
            size = len(nums)
            dp = []
            for x in range(size):
                low, high = 0, len(dp) - 1
                while low <= high:
                    mid = (low + high) / 2
                    if dp[mid] < nums[x]:
                        low = mid + 1
                    else:
                        high = mid - 1
                if low < len(dp):
                    dp[low] = nums[x]
                else:
                    dp.append(nums[x])
            return len(dp)
                        
        envelopes.sort(cmp=lambda x,y: x[0]-y[0] if x[0]!=y[0] else y[1]-x[1])
        #yprint envelopes
        return lis_nlgn([envelopes[i][1] for i in xrange(len(envelopes))])