共计 1812 个字符，预计需要花费 5 分钟才能阅读完成。
读完本文，你能够去力扣拿下如下题目：
354. 俄罗斯套娃信封问题
———–
很多算法问题都须要排序技巧，其难点不在于排序自身，而是须要奇妙地排序进行预处理，将算法问题进行转换，为之后的操作打下基础。
信封嵌套问题就须要先按特定的规定排序，之后就转换为一个 最长递增子序列问题 的技巧来解决了。
一、题目概述
信封嵌套问题是个很有意思且经常出现在生活中的问题，先看下题目：
这道题目其实是最长递增子序列（Longes Increasing Subsequence，简写为 LIS）的一个变种，因为很显然，每次非法的嵌套是大的套小的，相当于找一个最长递增的子序列，其长度就是最多能嵌套的信封个数。
然而难点在于，规范的 LIS 算法只能在数组中寻找最长子序列，而咱们的信封是由 (w, h) 这样的二维数对模式示意的，如何把 LIS 算法使用过去呢？
读者兴许会想，通过 w × h 计算面积，而后对面积进行规范的 LIS 算法。然而稍加思考就会发现这样不行，比方 1 × 10 大于 3 × 3，然而显然这样的两个信封是无奈相互嵌套的。
二、解法
这道题的解法是比拟奇妙的：
先对宽度 w 进行升序排序，如果遇到 w 雷同的状况，则依照高度 h 降序排序。之后把所有的 h 作为一个数组，在这个数组上计算 LIS 的长度就是答案。
画个图了解一下，先对这些数对进行排序：
而后在 h 上寻找最长递增子序列：
这个子序列就是最优的嵌套计划。
这个解法的关键在于，对于宽度 w 雷同的数对，要对其高度 h 进行降序排序。因为两个宽度雷同的信封不能互相蕴含的，逆序排序保障在 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);
}对于最长递增子序列的寻找办法，在前文中具体介绍了动静布局解法, 并用扑克牌游戏解释了二分查找解法，本文就不开展了，间接套用算法模板：
/* 返回 nums 中 LIS 的长度 */
public int lengthOfLIS(int[] nums) {
int piles = 0, n = nums.length;
int[] top = new int[n];
for (int i = 0; i < n; i++) {
// 要解决的扑克牌
int poker = nums[i];
int left = 0, right = piles;
// 二分查找插入地位
while (left < right) {int mid = (left + right) / 2;
if (top[mid] >= poker)
right = mid;
else
left = mid + 1;
}
if (left == piles) piles++;
// 把这张牌放到牌堆顶
top[left] = poker;
}
// 牌堆数就是 LIS 长度
return piles;
} 为了清晰，我将代码分为了两个函数，你也能够合并，这样能够节省下 height 数组的空间。
此算法的工夫复杂度为 O(NlogN)，因为排序和计算 LIS 各须要 O(NlogN) 的工夫。
空间复杂度为 O(N)，因为计算 LIS 的函数中须要一个 top 数组。
三、总结
这个问题是个 Hard 级别的题目，难就难在排序，正确地排序后此问题就被转化成了一个规范的 LIS 问题，容易解决一些。
其实这种问题还能够拓展到三维，比如说当初不是让你嵌套信封，而是嵌套箱子，每个箱子有长宽高三个维度，请你算算最多能嵌套几个箱子？
咱们可能会这样想，先把前两个维度（长和宽）按信封嵌套的思路求一个嵌套序列，最初在这个序列的第三个维度（高度）找一下 LIS，应该能算出答案。
实际上，这个思路是谬误的。这类问题叫做「偏序问题」，回升到三维会使难度巨幅晋升，须要借助一种高级数据结构「树状数组」，有趣味的读者能够自行搜寻。
有很多算法问题都须要排序后进行解决，阿东正在进行整顿总结。心愿本文对你有帮忙。
