## 题目描述：

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]).

## 解题思路：

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

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)
``````

Pingbacks已关闭。