# 354. 俄罗斯套娃信封问题 (Hard)

## 问题描述

[354. 俄罗斯套娃信封问题][link] (Hard)

[link]: https://leetcode.cn/problems/russian-doll-envelopes/

给你一个二维整数数组 `envelopes` ，其中 `envelopes[i] = [wᵢ, hᵢ]` ，表示第 `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 <= 10⁵`
- `envelopes[i].length == 2`
- `1 <= wᵢ, hᵢ <= 10⁵`


## 解题思路

本题的第一反应肯定是排序，按照第数组的第一个维度升序排序，问题在于，第二个维度是应该升序还是降序呢？

首先，观察题目，题目要求是两个维度都必须严格小于才行，我自己做的时候就没观察到这一点，卡了很久，注意到这一点的话，其实就好想很多了。

我们先假设按照第二个升序排列，当我们选择了 $(w_i, h_i)$ 之后，那么我们就是要找满足 $(w_j, h_j)$ 两个维度都严格小于 $(w_i, h_i)$ 的最大的 $(w_j, h_j)$，这里就可以联系到 LIS 问题了。

到这里的话，就可以意识到应该按照第二维度降序排列了，因为按照第二维度降序排列的话，我们就可以完全转化成 $h_i$ 组成的数组的 LIS 问题了。

而如果是第二维度按照升序排列，那么 $(4, 5), (4, 6)$ 就都会选为 LIS 的一部分，与题目要求不符合。

按第二维度降序排列，能保证构成 LIS 时，相同的 $w$ 的信封只会有一个在 LIS 中。

## 代码

```cpp
class Solution {
  public:
    int Bfind(vector<int> &lis, int target, vector<vector<int>> &envelopes, int right) {
        int left = 0;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (lis[mid] < target) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        return left;
    }
    int maxEnvelopes(vector<vector<int>> &envelopes) {
        auto cmp = [](vector<int> &vec1, vector<int> &vec2) {
            if (vec1[0] == vec2[0]) {
                return vec1[1] >= vec2[1];
            }
            return vec1[0] < vec2[0];
        };
        sort(envelopes.begin(), envelopes.end(), cmp);
        int n = envelopes.size(), ans = 0;
        vector<int> lis(n);
        for (int i = 0; i < n; ++i) {
            int idx = Bfind(lis, envelopes[i][1], envelopes, ans);
            if (idx >= ans) {
                ++ans;
            }
            lis[idx] = envelopes[i][1];
        }
        return ans;
    }
};
```