问题描述
354. 俄罗斯套娃信封问题 (Hard)
给你一个二维整数数组 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 == 21 <= 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 中。
代码
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;
}
};