我们看一个经常出现在生活中的有趣问题，力扣第 354 题「俄罗斯套娃信封问题」，先看下题目：
给你一个二维整数数组 envelopes ，其中 envelopes[i] = [wi, hi] ，表示第 i 个信封的宽度和高度。
当另一个信封的宽度和高度都比这个信封大的时候，这个信封就可以放进另一个信封里，如同俄罗斯套娃一样。
请计算 最多能有多少个 信封能组成一组“俄罗斯套娃”信封（即可以把一个信封放到另一个信封里面）。
注意：不允许旋转信封。
示例 1：
输入： envelopes = [[5,4],[6,4],[6,7],[2,3]]
输出： 3
解释： 最多信封的个数为 3, 组合为: [2,3] ⇒ [5,4] ⇒ [6,7]。
示例 2：
输入： envelopes =[[1,1],[1,1],[1,1]] 输出： 1
提示：
1 <= envelopes.length <= 105envelopes[i].length == 21 <= wi, hi <= 105
这道题目其实是最长递增子序列的一个变种，因为每次合法的嵌套是大的套小的，相当于在二维平面中找一个最长递增的子序列，其长度就是最多能嵌套的信封个数。
前面说的标准 LIS 算法只能在一维数组中寻找最长子序列，而我们的信封是由 (w, h) 这样的二维数对形式表示的，如何把 LIS 算法运用过来呢？
这道题目其实是最长递增子序列的一个变种，因为每次合法的嵌套是大的套小的，相当于在二维平面中找一个最长递增的子序列，其长度就是最多能嵌套的信封个数。
前面说的标准 LIS 算法只能在一维数组中寻找最长子序列，而我们的信封是由 (w, h) 这样的二维数对形式表示的，如何把 LIS 算法运用过来呢？
读者也许会想，通过 w × h 计算面积，然后对面积进行标准的 LIS 算法。但是稍加思考就会发现这样不行，比如 1 × 10 大于 3 × 3，但是显然这样的两个信封是无法互相嵌套的。
这道题的解法比较巧妙：
先对宽度 w 进行升序排序，如果遇到 w 相同的情况，则按照高度 h 降序排序；之后把所有的 h 作为一个数组，在这个数组上计算 LIS 的长度就是答案。
画个图理解一下，先对这些数对进行排序：
然后在 h 上寻找最长递增子序列，这个子序列就是最优的嵌套方案：
那么为什么这样就可以找到可以互相嵌套的信封序列呢？稍微思考一下就明白了：
首先，对宽度 w 从小到大排序，确保了 w 这个维度可以互相嵌套，所以我们只需要专注高度 h 这个维度能够互相嵌套即可。
其次，两个 w 相同的信封不能相互包含，所以对于宽度 w 相同的信封，对高度 h 进行降序排序，保证二维 LIS 中不存在多个 w 相同的信封（因为题目说了长宽相同也无法嵌套）。
下面看解法代码：
// envelopes = [[w, h], [w, h]...]
public int maxEnvelopes(int[][] envelopes) {
int n = envelopes.length;
// 按宽度升序排列，如果宽度一样，则按高度降序排列
Arrays.sort(envelopes, new Comparator<int[]>()
{
public int compare(int[] a, int[] b) {
return a[0] == b[0] ?
b[1] - a[1] : a[0] - b[0];
}
});
// 对高度数组寻找 LIS
int[] height = new int[n];
for (int i = 0; i < n; i++)
height[i] = envelopes[i][1];
return lengthOfLIS(height);
}
int lengthOfLIS(int[] nums) {
// 见前文
}动态规划设计：最长递增子序列 | labuladong 的算法笔记
为了清晰，我将代码分为了两个函数，你也可以合并，这样可以节省下 height 数组的空间。
由于增加了测试用例，这里必须使用二分搜索版的 lengthOfLIS 函数才能通过所有测试用例。这样的话算法的时间复杂度为 O(NlogN)，因为排序和计算 LIS 各需要 O(NlogN) 的时间，加到一起还是 O(NlogN)；空间复杂度为 O(N)，因为计算 LIS 的函数中需要一个 top 数组。为了清晰，我将代码分为了两个函数，你也可以合并，这样可以节省下 height 数组的空间。
由于增加了测试用例，这里必须使用二分搜索版的 lengthOfLIS 函数才能通过所有测试用例。这样的话算法的时间复杂度为 O (NlogN)，因为排序和计算 LIS 各需要 O (NlogN) 的时间，加到一起还是 O (NlogN)；空间复杂度为 O (N)，因为计算 LIS 的函数中需要一个 top 数组。