- LeetCode354：俄罗斯套娃信封问题
- 刷题时间：2022-01-13
- 力扣难度：Hard
- 个人难度：Hard
- 数据结构：数组、LIS最长递增子序列
- 算法：动态规划、二分查找、贪心
- 相似题型：LIS问题
LeetCode354俄罗斯套娃信封问题：「LIS问题：序列DP & 二分 & 贪心」&「树状数组」
1. 题目描述
题目：原题链接
- 给你一个二维整数数组 envelopes ，其中 $envelopes[i] = [wi, hi]$ ，表示第 i 个信封的宽度和高度。
- 当另一个信封的宽度和高度都比这个信封大的时候，这个信封就可以放进另一个信封里，如同俄罗斯套娃一样。
- 请计算 最多能有多少个 信封能组成一组“俄罗斯套娃”信封（即可以把一个信封放到另一个信封里面）。
- 注意：不允许旋转信封。
输入输出规范
- 输入：信封的宽高二维数组
- 输出：可以嵌套的信封最大个数
- 数据量
- 1 <= envelopes.length <= 5000
- envelopes[i].length == 2
- 1 <= wi, hi <= 10000
输入输出示例
- 输入：envelopes = [[5,4],[6,4],[6,7],[2,3]]
- 输出：3
2. 方法一：线性DP
思路：
dp[i]表示以第 i 个元素结尾的最长递增子序列的长度- 分析本题的核心是将信封的宽高进行比较，找到宽高都逐渐递增的最长的序列，即可以转化为LIS问题
- 首先，原本的元素是无序的，所以要对宽度排序来确保宽度上是已经满足要求的
- 此时可以发现，对于第 i 个信封(元素)，其可以装入的信封个数仅仅依赖于排在其前面的 i - 1 个信封，即满足线性DP的思路，
- 由此确定解题方法为线性DP，外层循环对应每个信封，内层循环去确定当前信封前面的信封是否可以装入
- 状态定义：
dp[i]表示以第 i 个信封结尾的最长信封可嵌套的大小 - 边界条件：每个元素至少可以存放自己，所以要在外层循环时初始化DP数组为1
- 状态转移方程：在内层循环时，判断信封 j 可否装入(小于)信封 i ，可以时，
dp[i] = max(dp[i], dp[j] + 1) - 最终结果：
max(dp)就是最大信封嵌套大小
题解
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18// 方法一：线性DP
public int maxEnvelopes(int[][] envelopes) {
if(envelopes == null || envelopes.length == 0) return 0;
int n = envelopes.length;
int[] dp = new int[n];
Arrays.sort(envelopes, (a, b) -> a[0] - b[0]);
int maxCount = 0;
for (int i = 0; i < n; i++) {
dp[i] = 1;
for (int j = 0; j < i; j++) {
if(envelopes[j][0] < envelopes[i][0] && envelopes[j][1] < envelopes[i][1]) {
dp[i] = Math.max(dp[i], dp[j] + 1);
}
}
maxCount = Math.max(maxCount,dp[i]);
}
return maxCount;
}复杂度分析：n 是信封数组的大小
- 时间复杂度：$O(n^2)$
- 空间复杂度：$O(n)$
注意：虽然在DP前就已经按照宽度进行的排序，但是DP中仍然需要对宽度大小进行判断，因为存在宽度相等的情形
3. 方法二：序列DP & 二分 & 贪心
思路：
dp[i]表示长度为 i 的最长递增子序列的末尾元素- 线性DP的时间复杂度为指数级，虽然思路简单但是效率不高，可能发生TLE超时问题，因此需要进行优化
- 对于LIS问题而言，指数级复杂度主要是由于DP过程中查找前 i 个元素中比当前元素小的过程是线性的
- 因此优化的思路一方面是通过二分优化到对数级，另一方面是直接优化到常数级
- 对数级查找即二分查找，而常数级查找需要借用哈希表，又因为哈希表不支持范围查找，所以确定本题通过二分将复杂度优化为对数级，相当于在找前一个信封
- 内层循环的查找方式改为二分，相应的DP状态定义也发生了改变
- 状态定义：
dp[i]表示长度为 i 的最大可嵌套信封序列的末尾(最外面的)元素，元素通过信封高度表示 - 状态转移方程
- 当新元素的宽度与前面元素的宽度不同时，首先判断此时表示LIS长度的DP数组的长度与此时LIS的真实长度(len变量)是否相等，相等时对高度DP数组进行末尾添加，不相等时对高度DP数组中的对应位置替换为同一宽度下的最小高度
- 当新元素的宽度和前面元素相同时，直接通过二分查找该元素应该插入到表示高度元素的DP数组的哪个位置，并且将该索引存入到表示LIS长度的DP数组中，此时不更新高度DP数组
题解
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// 方法二：序列DP & 二分 & 贪心
public int maxEnvelopes(int[][] envelopes){
if (envelopes == null || envelopes.length == 0) return 0;
int n = envelopes.length;
Arrays.sort(envelopes, (a, b) -> a[0] - b[0]);
int[] dp_len = new int[n]; // 以序列中第 i 个元素结尾的LIS的最长长度
int[] dp_height = new int[n]; // 长度为 i 的LIS的末尾最小元素，只存了信封的高
Arrays.fill(dp_height, Integer.MAX_VALUE);
dp_height[0] = 0;
int maxCount = 1;
// widthIndex 表示前一种宽度的开始索引
int widthIndex = 0;
int len = 1;
for (int i = 0; i < n; i++) {
int height = envelopes[i][1];
// 1. 遍历到的新元素的宽度与 LIS结尾元素数组dp_height中最新的宽度不同的情况，此时更新 dp_height
if(envelopes[i][0] != envelopes[widthIndex][0]) {
// 比较当前元素与前一种宽度的所有元素有元素结尾的LIS长度与目前的长度是否相等
while (widthIndex < i) {
int prevLen = dp_len[widthIndex]; // 前一种宽度的所有元素有元素结尾的LIS长度与目前的长度
if(prevLen == len) {
// 相等在 dp_height 的末尾添加元素
dp_height[len++] = envelopes[widthIndex][1];
}else {
// 不相等时，LIS长度不变，dp_height 中对应长度的位置替换为前一种宽度中的最小值高度
dp_height[prevLen] = Math.min(dp_height[prevLen], envelopes[widthIndex][1]);
}
widthIndex++;
}
}
// 2. 两者宽度不相等时，通过二分的方式来寻找当前元素的高度应该替换、插入到 dp_height 数组的哪个位置，但是
int index = binarySearch(dp_height, height, 0, len);
dp_len[i] = index;
maxCount = Math.max(maxCount, dp_len[i]);
}
return maxCount;
}
private int binarySearch(int[] dp, int height, int left, int right) {
while (right > left) {
int mid = (right - left) / 2 + left;
if (dp[mid] >= height) {
right = mid;
} else {
left = mid + 1;
}
}
return left;
}复杂度分析：n 是信封数组的大小
- 时间复杂度：$O(nlogn)$
- 空间复杂度：$O(n)$
注意：由于本题不是一维的LIS问题，而是要同时满足宽度和高度，所以需要两个dp数组来分别表示LIS长度和LIS末尾最小元素
扩展. 方法三：序列DP & 树状数组 & 贪心
思路：树状数组来实现二分
- 与方法二的思路一样，为了优化复杂度，需要引入二分的操作，树状数组同样可以实现二分的过程
- 其中，需要对信封的高度进行离散化，具体做法是
- 先遍历高度，添加到哈希表中去重
- 在创建一个数组，将高度从哈希表中获取并赋值给数组，并排序
- 通过二分查找，在该数组中查找每一个信封的高度的索引并赋值给高度
- 创建tree数组模拟树状数组，创建DP数组，表示以当前元素结尾的最大长度
- 遍历所有元素，同样对于相等的宽度，不更新tree数组，其他与方法二基本一致
- 实际上就是用树状数组代替了普通的DP数组，不过需要对原始数据做一些离散化处理
题解
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// 方法三：树状数组
int[] tree;
int lowbit(int x) {
return x & -x;
}
public int maxEnvelopes3(int[][] envelopes) {
if (envelopes == null || envelopes.length == 0) return 0;
int n = envelopes.length;
Arrays.sort(envelopes, (a, b) -> a[0] - b[0]);
// 先将所有的 h 进行离散化
Set<Integer> set = new HashSet<>();
for (int i = 0; i < n; i++) set.add(envelopes[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++) envelopes[i][1] = Arrays.binarySearch(hs, envelopes[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 (envelopes[i][0] != envelopes[j][0]) {
// 限制 j 不能越过 i，确保 tree 数组中只会出现第 i 个信封前的「历史信封」
while (j < i) {
for (int u = envelopes[j][1]; u <= cnt; u += lowbit(u)) {
tree[u] = Math.max(tree[u], f[j]);
}
j++;
}
}
f[i] = 1;
for (int u = envelopes[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;
}复杂度分析：n 是信封数组的大小
- 时间复杂度：$O(nlogn)$
- 空间复杂度：$O(n)$
本文作者：
Chthollists
发布时间： 2022-01-13 17:33:16
最后更新： 2022-01-21 23:09:05
本文标题： LeetCode354俄罗斯套娃信封问题：「LIS问题：序列DP & 二分 & 贪心」&「树状数组」
本文链接： https://chthollists.github.io/post/519cee51.html
版权声明： 本作品采用 CC BY-NC-SA 4.0 许可协议进行许可。转载请注明作者和出处！
发布时间： 2022-01-13 17:33:16
最后更新： 2022-01-21 23:09:05
本文标题： LeetCode354俄罗斯套娃信封问题：「LIS问题：序列DP & 二分 & 贪心」&「树状数组」
本文链接： https://chthollists.github.io/post/519cee51.html
版权声明： 本作品采用 CC BY-NC-SA 4.0 许可协议进行许可。转载请注明作者和出处！
