# 信封嵌套问题
![](../pictures/souyisou.png) 相关推荐: * [讲两道常考的阶乘算法题](https://labuladong.gitbook.io/algo) * [状态压缩:对动态规划进行降维打击](https://labuladong.gitbook.io/algo) 读完本文,你不仅学会了算法套路,还可以顺便去 LeetCode 上拿下如下题目: [354.俄罗斯套娃信封问题](https://leetcode-cn.com/problems/russian-doll-envelopes) **-----------** 很多算法问题都需要排序技巧,其难点不在于排序本身,而是需要巧妙地排序进行预处理,将算法问题进行转换,为之后的操作打下基础。 信封嵌套问题就需要先按特定的规则排序,之后就转换为一个 [最长递增子序列问题](https://labuladong.gitbook.io/algo),可以用前文 [二分查找详解](https://labuladong.gitbook.io/algo) 的技巧来解决了。 ### 一、题目概述 信封嵌套问题是个很有意思且经常出现在生活中的问题,先看下题目: ![title](../pictures/%E4%BF%A1%E5%B0%81%E5%B5%8C%E5%A5%97/title.png) 这道题目其实是最长递增子序列(Longes Increasing Subsequence,简写为 LIS)的一个变种,因为很显然,每次合法的嵌套是大的套小的,相当于找一个最长递增的子序列,其长度就是最多能嵌套的信封个数。 但是难点在于,标准的 LIS 算法只能在数组中寻找最长子序列,而我们的信封是由 `(w, h)` 这样的二维数对形式表示的,如何把 LIS 算法运用过来呢? ![0](../pictures/%E4%BF%A1%E5%B0%81%E5%B5%8C%E5%A5%97/0.jpg) 读者也许会想,通过 `w × h` 计算面积,然后对面积进行标准的 LIS 算法。但是稍加思考就会发现这样不行,比如 `1 × 10` 大于 `3 × 3`,但是显然这样的两个信封是无法互相嵌套的。 ### 二、解法 这道题的解法是比较巧妙的: **先对宽度 `w` 进行升序排序,如果遇到 `w` 相同的情况,则按照高度 `h` 降序排序。之后把所有的 `h` 作为一个数组,在这个数组上计算 LIS 的长度就是答案。** 画个图理解一下,先对这些数对进行排序: ![1](../pictures/%E4%BF%A1%E5%B0%81%E5%B5%8C%E5%A5%97/1.jpg) 然后在 `h` 上寻找最长递增子序列: ![2](../pictures/%E4%BF%A1%E5%B0%81%E5%B5%8C%E5%A5%97/2.jpg) 这个子序列就是最优的嵌套方案。 这个解法的关键在于,对于宽度 `w` 相同的数对,要对其高度 `h` 进行降序排序。因为两个宽度相同的信封不能相互包含的,逆序排序保证在 `w` 相同的数对中最多只选取一个。 下面看代码: ```java // envelopes = [[w, h], [w, h]...] public int maxEnvelopes(int[][] envelopes) { int n = envelopes.length; // 按宽度升序排列,如果宽度一样,则按高度降序排列 Arrays.sort(envelopes, new Comparator======其他语言代码======