俄罗斯套娃信封问题
俄罗斯套娃问题
非常感谢labuladong的博客分享！让学习算法不再困难。
题目
给定一个二维整数列表 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 <= 10^5 \\ envelopes[i].length == 2 \\ 1 <= w_i, h_i <= 10^5
问题分析
题目意图凝练深刻,即为嵌套问题;其中每个信封必须容纳前一编号的信封,并与最长递增子序列变形有关.
本题需要对比两个维度（即宽度与高度），这样的对比具有一定的难度。鉴于此，我们可以选择固定其中一个维度仅对另一个维度进行分析从而将这个问题转化为最长递增子序列 问题。
如何固定住其中一维呢？
这里选择固定信封的宽度
可以将信封数组的第一列按照从小到大进行排序，这样就固定住了一维
那么高度要从大到小进行排序。
为何采用逆序排列？官方题解指出，在这种情况下 h 值无法形成长度超过 1 的严格递增序列。其含义是子序列必须保持严格的单调递增状态，并且不允许存在相等的元素。因此其最长可能长度仅为1，即相邻元素之间的差值至少为 1 即可满足条件。
以下通过图形进行分析，便于理解
高度降序可以保证不会出现大小相同的信封进行套娃
代码
C++
class Solution {
public:
int maxEnvelopes(vector<vector<int>>& envelopes) {
int len = envelopes.size();
sort(envelopes.begin(), envelopes.end(), [] (const auto& e1, const auto& e2){
return e1[0] < e2[0] || (e1[0] == e2[0] && e1[1] > e2[1]);
});
vector<int> dp(len, 1);
for (int i = 1; i < len; i++) {
for (int j = 0; j < i; j++) {
if (envelopes[j][1] < envelopes[i][1]) {
dp[i] = max(dp[i], dp[j] + 1);
}
}
}
return *max_element(dp.begin(), dp.end());
}
};
AI写代码java
class Solution {
int LISLength(int[] arr) {
int[] dp = new int[arr.length + 1];
Arrays.fill(dp, 1);
int _max = 1;
for (int i = 1; i < arr.length; i++) {
for (int j = 0; j < i; j++) {
if (arr[j] < arr[i]) {
dp[i] = Math.max(dp[i], dp[j] + 1);
_max = Math.max(_max, dp[i]);
}
}
}
return _max;
}
public int maxEnvelopes(int[][] envelopes) {
int length = envelopes.length;
Arrays.sort(envelopes, new Comparator<int[]>(){
public int compare(int[] a, int[] b) {
if (a[0] == b[0]) {
return b[1] - a[1];
} else {
return a[0] - b[0];
}
}
});
int[] temp = new int[envelopes.length];
for (int i = 0; i < envelopes.length; i++) {
temp[i] = envelopes[i][1];
}
return LISLength(temp);
}
}
AI写代码