题目描述：
给出一个二维整数数组 envelopes，其中envelopes[i]=[wi,hi]，表示第 $i$ 个信封的宽度和高度。
当另一个信封的宽度和高度都比这个信封大的时候，这个信封才能放进另一个信封里。
请计算最多能有多少个信封能组成一组信封。不允许旋转。
数据范围： $1\le n \le 10^5$
题解：
二维LIS问题，而且只能使用 $O(n\log(n))$ 做法。
需要先对第一维排序，保证第一维顺序，然后在第二维上做二分LIS。
并且要注意，第一维相等时，第二维需要逆序排，这样的话才会保证只会取到一个，不会把两个都取到。
记录答案：
同样使用 $pre[i]$ 表示当前 $envelopes[i]$ 接在末尾时的前一个下标，这样的话在二分查找到更新时，需要 $pre[i] = pre[dp[index]]$ 。因为 $index$ 要被替换掉，因此 $pre[i]$ 需要被更新为 $pre[index]$ 。
代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
| auto optimize_cpp_stdio = []()
{
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cout.tie(nullptr);
return 0;
}();
class Solution
{
public:
vector<int> pre;
vector<pair<int, int>> dp;
int maxEnvelopes(vector<vector<int>> &envelopes)
{
auto old = envelopes;
int len = 1, n = envelopes.size();
pre.resize(n, -1);
dp.resize(n + 1, {0, 0});
sort(envelopes.begin(), envelopes.end(), [&](const vector<int> &x, const vector<int> &y)
{ if(x[0] != y[0]) return x[0] < y[0];
else return x[1] > y[1]; });
dp[0] = {envelopes[0][1], 0};
for (int i = 1; i < n; ++i)
{
if (envelopes[i][1] > dp[len - 1].first)
{
pre[i] = dp[len - 1].second;
dp[len++] = {envelopes[i][1], i};
}
else
{
int index = lower_bound(dp.begin(), dp.begin() + len, make_pair(envelopes[i][1], i),
[&](const pair<int, int> &x, const pair<int, int> &y)
{
return x.first < y.first;
}) -
dp.begin();
pre[i] = pre[dp[index].second];
dp[index] = {envelopes[i][1], i};
}
}
vector<int> ans;
int tmp = dp[len - 1].second;
while (tmp != -1)
{
ans.push_back(tmp);
tmp = pre[tmp];
}
reverse(ans.begin(), ans.end());
for (int i = 0; i < len; ++i)
{
cout << envelopes[ans[i]][0] << ", " << envelopes[ans[i]][1] << endl;
}
return len;
}
};
|