602. Russian Doll Envelopes
2019-07-21 本文已影响0人
鸭蛋蛋_8441
Description
Give 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.
Find the maximum number of nested layers of envelopes.
Example
Example 1:
Input：[[5,4],[6,4],[6,7],[2,3]]
Output：3
Explanation：
the maximum number of envelopes you can Russian doll is 3 ([2,3] => [5,4] => [6,7]).
Example 2:
Input：[[4,5],[4,6],[6,7],[2,3],[1,1]]
Output：4
Explanation：
the maximum number of envelopes you can Russian doll is 4 ([1,1] => [2,3] => [4,5] / [4,6] => [6,7]).
思路：
先将宽度正序排之后，高度逆序排（这个很关键），然后求高度的最长上升子序列，同76题即为一样的。另外注意用Lambda函数排序的写法。
代码：
