题目描述：

LeetCode 354. Russian Doll Envelopes

You have a number of envelopes with widths and heights given as a pair of integers (w, h). One envelope can fit into another if and only if both the width and height of one envelope is greater than the width and height of the other envelope.

What is the maximum number of envelopes can you Russian doll? (put one inside other)

Example:

Given envelopes = [[5,4],[6,4],[6,7],[2,3]], the maximum number of envelopes you can Russian doll is 3 ([2,3] => [5,4] => [6,7]).

题目大意：

给定一组以整数对(w, h)表示的信封的宽和高。一个信封可以装下另一个信封，当且仅当前者的宽和高均严格大于后者。

最多可以嵌套多少层信封（有点像俄罗斯套娃）？

测试用例如题目描述。

解题思路：

参考Longest Increasing Subsequence（最长递增子序列）的解法。

以输入envelopes其中的一个维度进行排序，对另外一个维度求解LIS即可。

1. 对输入的envelopes进行排序：首先比较宽度，宽度小的在前；宽度相同时，高度大的在前（这样处理可以避免相同宽度的信封被重复统计）

2. 利用二分查找维护一个递增队列，以高度作为比较条件。

由于LeetCode OJ的最大测试用例规模超过4000，O(n ^ 2)的解法会超时。

Python代码：

class Solution(object):
    def maxEnvelopes(self, envelopes):
        """
        :type envelopes: List[List[int]]
        :rtype: int
        """
        nums = sorted(envelopes, 
                      cmp = lambda x,y: x[0] - y[0] if x[0] != y[0] else y[1] - x[1])
        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][1] < nums[x][1]:
                    low = mid + 1
                else:
                    high = mid - 1
            if low < len(dp):
                dp[low] = nums[x]
            else:
                dp.append(nums[x])
        return len(dp)

 

本文链接：http://bookshadow.com/weblog/2016/06/07/leetcode-russian-doll-envelopes/
请尊重作者的劳动成果，转载请注明出处！书影博客保留对文章的所有权利。

如果您喜欢这篇博文，欢迎您捐赠书影博客： ，查看支付宝二维码