信封嵌套问题.md

# 信封嵌套问题


<p align='center'>
<a href="https://github.com/labuladong/fucking-algorithm" target="view_window"><img alt="GitHub" src="https://img.shields.io/github/stars/labuladong/fucking-algorithm?label=Stars&style=flat-square&logo=GitHub"></a>
<a href="https://www.zhihu.com/people/labuladong"><img src="https://img.shields.io/badge/%E7%9F%A5%E4%B9%8E-@labuladong-000000.svg?style=flat-square&logo=Zhihu"></a>
<a href="https://i.loli.net/2020/10/10/MhRTyUKfXZOlQYN.jpg"><img src="https://img.shields.io/badge/公众号-@labuladong-000000.svg?style=flat-square&logo=WeChat"></a>
<a href="https://space.bilibili.com/14089380"><img src="https://img.shields.io/badge/B站-@labuladong-000000.svg?style=flat-square&logo=Bilibili"></a>
</p>

![](../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<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);
}
```

关于最长递增子序列的寻找方法，在前文中详细介绍了动态规划解法,并用扑克牌游戏解释了二分查找解法，本文就不展开了，直接套用算法模板：

```java
/* 返回 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，应该能算出答案。

实际上，这个思路是错误的。这类问题叫做「偏序问题」，上升到三维会使难度巨幅提升，需要借助一种高级数据结构「树状数组」，有兴趣的读者可以自行搜索。

有很多算法问题都需要排序后进行处理，阿东正在进行整理总结。希望本文对你有帮助。

**＿＿＿＿＿＿＿＿＿＿＿＿＿**

**刷算法，学套路，认准 labuladong，公众号和 [在线电子书](https://labuladong.gitbook.io/algo/) 持续更新最新文章**。

**本小抄即将出版，微信扫码关注公众号，后台回复「小抄」限时免费获取，回复「进群」可进刷题群一起刷题，带你搞定 LeetCode**。

<p align='center'>
<img src="../pictures/qrcode.jpg" width=200 >
</p>

======其他语言代码======

[354.俄罗斯套娃信封问题](https://leetcode-cn.com/problems/russian-doll-envelopes)



### javascript

[300. 最长递增子序列](https://leetcode-cn.com/problems/longest-increasing-subsequence/)

给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。

子序列是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。

```js
/**
 * @param {number[]} nums
 * @return {number}
 */
let lengthOfLIS = function(nums) {
    let top = new Array(nums.length);

    // 牌堆数初始化为 0
    let piles = 0;

    for (let i = 0; i < nums.length; i++) {
        // 要处理的扑克牌
        let poker = nums[i];

        /***** 搜索左侧边界的二分查找 *****/
        let left = 0, right = piles;
        while (left < right) {
            let mid = (left + right) / 2;
            if (top[mid] > poker) {
                right = mid;
            } else if (top[mid] < poker) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        /*********************************/

        // 没找到合适的牌堆，新建一堆
        if (left === piles) piles++;

        // 把这张牌放到牌堆顶
        top[left] = poker;
    }

    // 牌堆数就是 LIS 长度
    return piles;
};
```



[354.俄罗斯套娃信封问题](https://leetcode-cn.com/problems/russian-doll-envelopes)

```js
/**
 * @param {number[]} nums
 * @return {number}
 */
let lengthOfLIS = function(nums) {
    let top = new Array(nums.length);

    // 牌堆数初始化为 0
    let piles = 0;

    for (let i = 0; i < nums.length; i++) {
        // 要处理的扑克牌
        let poker = nums[i];

        /***** 搜索左侧边界的二分查找 *****/
        let left = 0, right = piles;
        while (left < right) {
            let mid = Math.floor((left + right) / 2);
            if (top[mid] > poker) {
                right = mid;
            } else if (top[mid] < poker) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        /*********************************/

        // 没找到合适的牌堆，新建一堆
        if (left === piles) piles++;

        // 把这张牌放到牌堆顶
        top[left] = poker;
    }

    // 牌堆数就是 LIS 长度
    return piles;
};

/**
 * @param {number[][]} envelopes
 * @return {number}
 */
var maxEnvelopes = function (envelopes) {
    let n = envelopes.length;
    // 按宽度升序排列，如果宽度一样，则按高度降序排列
    envelopes.sort((a, b) => {
        return a[0] === b[0] ? b[1] - a[1] : a[0] - b[0];
    })
   
    // 对高度数组寻找 LIS
    let height = new Array(n);
    for (let i = 0; i < n; i++)
        height[i] = envelopes[i][1];

    return lengthOfLIS(height);
};

```