华为报批
之前有过一些华为秋招的薪资爆料，但那大多数都是"前菜"性质，毕竟还没有正式报批，大多都只是 HR 根据以外经验，给候选人的大概参考范围。
但就在昨天下午，华为开始陆续正式报批了，并承诺会在本周六（11-30）发正式 offer。
那些在本次华为秋招经历了两轮（甚至三轮）保温的孩子，悬着的心总算可以定下来了。
从最新的报批情况来看，和我们此前的爆料区别不大。
这里再简单看看最新爆料：
上海-通用软件开发：985 硕，20k * 16（年包 32W），职级 13a/14c/14b； 上海-通用软件开发：985 硕，（22k~24k）* 16（年包 35W~38W），职级 14a； 上海-算法：985 硕，（28k~31k）* 16（年包 45W~50W），职级 15a；
也有部分同学，在经历了漫长的"爱信等"阶段，最终对评级不满意，甚至报批失败。
如果是报批失败，那没办法，估计有转折的可能性也不大。
但如果是对定级不满意，可以尝试一下去 A 一下（网上已经有成功从 13a/14c 的定级 A 到 14a 的）。
但即使最终 A 不成功，我觉得问题也不大，一般正常情况，入职两年左右也能升到 14 级。
...
回归主题。
来一道经典算法题。
题目描述
平台：LeetCode
题号：354
给你一个二维整数数组 envelopes，其中 ，表示第 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
【原数据结构范围】提示：
无
【题目更新后数据范围】提示：
动态规划
这是一道经典的 DP 模型题目：最长上升子序列（LIS）。
首先我们先对 envelopes 进行排序，确保信封是从小到大进行排序。
问题就转化为我们从这个序列中选择 k 个信封形成新的序列，使得新序列中的每个信封都能严格覆盖前面的信封（宽高都严格大于）。
我们可以定义状态 为考虑前 i 个物品，并以第 个物品为结尾的最大值。
对于每个 而言，最小值为 ，代表只选择自己一个信封。
那么对于一般的 该如何求解呢？因为第 i 件物品是必须选择的。我们可以枚举前面的 件物品，哪一件可以作为第 件物品的上一件物品。
在前 件物品中只要有符合条件的，我们就使用 更新 。
然后在所有方案中取一个 max 即是答案。
❝由于 LC 补充了数据范围 & 样例，该做法现已 TLE。
❞
Java 代码：
class Solution {
public int maxEnvelopes(int[][] es) {
int n = es.length, ans = 1;
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 个物品为结尾的最大值
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 记录当前记录到的最大长度。
还是不理解？没关系，我们可以直接看看代码，我把基本逻辑写在了注释当中（你的重点应该落在对 数组的理解上）。
Java 代码：
class Solution {
public int maxEnvelopes(int[][] es) {
int n = es.length, ans = 1;
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;
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;
}
}
C++ 代码：
class Solution {
public:
int maxEnvelopes(vector<vector<int>>& es) {
int n = es.size(), ans = 1;
if (n == 0) return n;
sort(es.begin(), es.end(), [](const vector<int>& a, const vector<int>& b) {
return a[0] < b[0];
});
vector<int> f(n, 0);
vector<int> g(n, INT_MAX);
g[0] = 0;
for (int i = 0, j = 0, len = 1; i < n; i++) {
if (es[i][0] != es[j][0]) {
while (j < i) {
int prev = f[j], cur = es[j][1];
if (prev == len) {
g[len++] = cur;
} else {
g[prev] = min(g[prev], cur);
}
j++;
}
}
int l = 0, r = len;
while (l < r) {
int mid = l + r >> 1;
if (es[i][1] <= g[mid]) r = mid;
else l = mid + 1;
}
f[i] = r;
ans = 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 值。
Java 代码：
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 会员优惠通道目前仍可用 ~
使用福利优惠通道 leetcode.cn/premium/?promoChannel=acoier，年度会员 有效期额外增加两个月，季度会员 有效期额外增加两周，更有超大额专属 🧧 和实物 🎁 福利每月发放。
我是宫水三叶，每天都会分享算法知识，并和大家聊聊近期的所见所闻。
欢迎关注，明天见。
