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

一句话题意

有n个信封，每个信封都有自己的宽高，并且当一个信封的宽高均严格大于另一个信封的宽高时，可以将后者套入前者中。

现在给定若干个信封的宽高，问最多可以有几层的嵌套信封（说白了就是“俄罗斯套娃”）。

解题思路

跟最长上升子序列很像，不过判断条件有两个，宽度跟高度而已。

所以可以选择其中一个进行排序，比如宽度。这时序列里前面的宽度都小于后面的，我们再对高度做最长子序列即可。

时间复杂度n^2