题目形容
这是 LeetCode 上的 「354. 俄罗斯套娃信封问题」，难度为 「艰难」。
给你一个二维整数数组 envelopes，其中 envelopes[i] = [wi, hi]，示意第 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 <= 5000
- envelopes[i].length == 2
- 1 <= wi, hi <=
动静布局
这是一道经典的 DP 模型题目：最长回升子序列（LIS）。
首先咱们先对 envelopes 进行排序，确保信封是从小到大进行排序。
问题就转化为咱们从这个序列中抉择 k 个信封造成新的序列，使得新序列中的每个信封都能严格笼罩后面的信封（宽高都严格大于）。
咱们能够定义状态 为思考前 i 个物品，并以第 个物品为结尾的最大值。
对于每个 而言，最小值为，代表只抉择本人一个信封。
那么对于个别的 该如何求解呢？因为第 i 件物品是必须抉择的。咱们能够枚举后面的 件物品，哪一件能够作为第 件物品的上一件物品。
在前 件物品中只有有符合条件的，咱们就应用 更新。
而后在所有计划中取一个 max 即是答案。
代码：
class Solution {public int maxEnvelopes(int[][] es) {
int n = es.length;
if (n == 0) return n;
// 因为咱们在找第 i 件物品的前一件物品时，会对后面的 i - 1 件物品都遍历一遍，因而第二维（高度）排序与否都不影响
Arrays.sort(es, (a, b)->a[0]-b[0]);
int[] f = new int[n]; // f(i) 为思考前 i 个物品，并以第 i 个物品为结尾的最大值
int ans = 1;
for (int i = 0; i < n; i++) {// 对于每个 f[i] 都满足最小值为 1
f[i] = 1;
// 枚举第 i 件物品的前一件物品，for (int j = i - 1; j >= 0; j--) {// 只有有满足条件的前一件物品，咱们就尝试应用 f[j] + 1 更新 f[i]
if (check(es, j, i)) {f[i] = Math.max(f[i], f[j] + 1);
}
}
// 在所有的 f[i] 中取 max 作为 ans
ans = Math.max(ans, f[i]);
}
return ans;
}
boolean check(int[][] es, int mid, int i) {return es[mid][0] < es[i][0] && es[mid][1] < es[i][1];
}
}
- 工夫复杂度：
- 空间复杂度：
二分 + 动静布局
上述计划其实算是一个奢侈计划，复杂度是 的，也是我最先想到思路，然而题目没有给出数据范畴，也不晓得能不能过。
气宇轩昂交了一个竟然过了。
上面讲下其余优化解法。
首先还是和之前一样，咱们能够通过复杂度剖析来想优化方向。
指数算法往下优化就是对数解法或者线性解法。
仔细观察奢侈解法，其实可优化的中央次要就是找第 件物品的前一件物品的过程。
如果想要放慢这个查找过程，咱们须要应用某种数据结构进行记录。
并且是边迭代边更新数据结构外面的内容。
首先因为咱们对 w 进行了排序（从小到大），而后迭代也是从返回后进行，因而咱们只须要保障迭代过程中，对于 w 雷同的数据不更新，就能保障 g 中只会呈现满足 w 条件的信封。
到这一步，还须要用到的货色有两个：一个是 h，因为只有 w 和 h 都同时满足，咱们能力退出回升序列中；一个是信封所对应的回升序列长度，这是咱们减速查找的外围。
咱们应用数组 g 来记录，示意长度为 的最长回升子序列的中的最小「信封高度」，同时须要应用 len 记录以后记录到的最大长度。
还是不了解？没关系，咱们能够间接看看代码，我把根本逻辑写在了正文当中（你的重点应该落在对 数组的了解上）。
代码：
class Solution {public int maxEnvelopes(int[][] es) {
int n = es.length;
if (n == 0) return n;
// 因为咱们应用了 g 记录高度，因而这里只需将 w 从小达到排序即可
Arrays.sort(es, (a, b)->a[0] - b[0]);
// f(i) 为思考前 i 个物品，并以第 i 个物品为结尾的最大值
int[] f = new int[n];
// g(i) 记录的是长度为 i 的最长回升子序列的最小「信封高度」int[] g = new int[n];
// 因为要取 min，用一个足够大（不可能）的高度初始化
Arrays.fill(g, Integer.MAX_VALUE);
g[0] = 0;
int ans = 1;
for (int i = 0, j = 0, len = 1; i < n; i++) {
// 对于 w 雷同的数据，不更新 g 数组
if (es[i][0] != es[j][0]) {
// 限度 j 不能越过 i，确保 g 数组中只会呈现第 i 个信封前的「历史信封」while (j < i) {int prev = f[j], cur = es[j][1];
if (prev == len) {
// 与以后长度统一了，阐明回升序列多减少一位
g[len++] = cur;
} else {
// 始终保留最小的「信封高度」，这样能够确保有更多的信封能够与其行程回升序列
// 举例：同样是回升长度为 5 的序列，保留最小高度为 5 记录（而不是保留任意的，比方 10），这样之后高度为 7 8 9 的信封都能造成序列；g[prev] = Math.min(g[prev], cur);
}
j++;
}
}
// 二分过程
// g[i] 代表的是回升子序列长度为 i 的「最小信封高度」int l = 0, r = len;
while (l < r) {
int mid = l + r >> 1;
// 令 check 条件为 es[i][1] <= g[mid]（代表 w 和 h 都严格小于以后信封）// 这样咱们找到的就是满足条件，最靠近数组中心点的数据（也就是满足 check 条件的最大下标）// 对应回 g[] 数组的含意，其实就是找到 w 和 h 都满足条件的最大回升长度
if (es[i][1] <= g[mid]) {r = mid;} else {l = mid + 1;}
}
// 更新 f[i] 与答案
f[i] = r;
ans = Math.max(ans, f[i]);
}
return ans;
}
}
- 工夫复杂度：对于每件物品都是通过「二分」找到其前一件物品。复杂度为
- 空间复杂度：
证实
咱们能够这样做的前提是 g 数组具备二段性，能够通过证实其具备「枯燥性」来实现。
当然这里指的是 g 被应用的局部，也就是 的局部。
咱们再回顾一下 g[] 数组的定义：示意长度为 的最长回升子序列的中的最小「信封高度」
例如 代表的含意是：
- 回升序列长度为 0 的最小历史信封高度为 0
- 回升序列长度为 1 的最小历史信封高度为 3
- 回升序列长度为 2 的最小历史信封高度为 4
- 回升序列长度为 3 的最小历史信封高度为 5
能够通过反证法来证实其枯燥性:
假如 不具备枯燥性，即至多有 (，令 ,)
显然与咱们的解决逻辑抵触。因为如果思考一个「最小高度」为 b 的信封可能凑出长度为 j 的回升序列，天然也能凑出比 j 短的回升序列，对吧？
举个🌰，咱们有信封：[[1,1],[2,2],[3,3],[4,4],[5,5]]，咱们能凑出很多种长度为 2 的回升序列计划，其中最小的计划是高度最小的计划是 [[1,1],[2,2]]。因而这时候 g[2] = 2，代表能凑出长度为 2 的回升序列所 「必须应用的信封」 的最小高度为 2。
这时候反过来思考，如果应用 [2,2] 可能凑出长度为 2 的回升序列，必然也能凑出长度为 1 的回升序列（删除后面的其余信封即可）。
推而广之，如果咱们有，也就是凑成长度为 j 必须应用的最小信封高度为 b。那么我必然可能保留高度为 b 的信封，删掉回升序列中的一些信封，凑成任意长度比 j 小的回升序列。
综上，（）与解决逻辑抵触，数组为严格枯燥回升数组。
既然 具备枯燥性，咱们能够通过「二分」找到恰满足 check 条件的最大下标（最大下标达标示意最长回升序列长度）。
树状数组 + 动静布局
在「二分 + 动静布局」的解法中，咱们通过「二分」来优化找第 个文件的前一个文件过程。
这个过程同样能通过「树状数组」来实现。
首先依然是对 w 进行排序，而后应用「树状数组」来保护 h 维度的前缀最大值。
对于 h 的高度，咱们只关怀多个信封之间的大小关系，而不关怀具体相差多少，咱们须要对 h 进行离散化。
通常应用「树状数组」都须要进行离散化，尤其是这里咱们自身就要应用 的空间来存储 dp 值。
代码：
class Solution {int[] tree;
int lowbit(int x) {return x & -x;}
public int maxEnvelopes(int[][] es) {
int n = es.length;
if (n == 0) return n;
// 因为咱们应用了 g 记录高度，因而这里只需将 w 从小达到排序即可
Arrays.sort(es, (a, b)->a[0] - b[0]);
// 先将所有的 h 进行离散化
Set<Integer> set = new HashSet<>();
for (int i = 0; i < n; i++) set.add(es[i][1]);
int cnt = set.size();
int[] hs = new int[cnt];
int idx = 0;
for (int i : set) hs[idx++] = i;
Arrays.sort(hs);
for (int i = 0; i < n; i++) es[i][1] = Arrays.binarySearch(hs, es[i][1]) + 1;
// 创立树状数组
tree = new int[cnt + 1];
// f(i) 为思考前 i 个物品，并以第 i 个物品为结尾的最大值
int[] f = new int[n];
int ans = 1;
for (int i = 0, j = 0; i < n; i++) {
// 对于 w 雷同的数据，不更新 tree 数组
if (es[i][0] != es[j][0]) {
// 限度 j 不能越过 i，确保 tree 数组中只会呈现第 i 个信封前的「历史信封」while (j < i) {for (int u = es[j][1]; u <= cnt; u += lowbit(u)) {tree[u] = Math.max(tree[u], f[j]);
}
j++;
}
}
f[i] = 1;
for (int u = es[i][1] - 1; u > 0; u -= lowbit(u)) {f[i] = Math.max(f[i], tree[u] + 1);
}
ans = Math.max(ans, f[i]);
}
return ans;
}
}
- 工夫复杂度：解决每个物品时更新「树状数组」复杂度为。整体复杂度为
- 空间复杂度：
最初
这是咱们「刷穿 LeetCode」系列文章的第 No.354 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，局部是有锁题，咱们将先将所有不带锁的题目刷完。
在这个系列文章外面，除了解说解题思路以外，还会尽可能给出最为简洁的代码。如果波及通解还会相应的代码模板。
为了不便各位同学可能电脑上进行调试和提交代码，我建设了相干的仓库：https://github.com/SharingSource/LogicStack-LeetCode。
在仓库地址里，你能够看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其余优选题解。