class Solution {
public:
int maxEnvelopes(vector<vector<int>>& envelopes) {
}
};
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 <= 105envelopes[i].length == 21 <= wi, hi <= 105相似题目
原站题解
golang 解法, 执行用时: 176 ms, 内存消耗: 21.2 MB, 提交时间: 2023-09-24 18:59:50
func maxEnvelopes(envelopes [][]int) int {
sort.Slice(envelopes, func(i, j int) bool {
a, b := envelopes[i], envelopes[j]
return a[0] < b[0] || a[0] == b[0] && a[1] > b[1]
})
f := []int{}
for _, e := range envelopes {
h := e[1]
if i := sort.SearchInts(f, h); i < len(f) {
f[i] = h
} else {
f = append(f, h)
}
}
return len(f)
}
javascript 解法, 执行用时: 188 ms, 内存消耗: 64.1 MB, 提交时间: 2023-09-24 18:59:37
/**
* @param {number[][]} envelopes
* @return {number}
*/
var maxEnvelopes = function(envelopes) {
if (envelopes.length === 0) {
return 0;
}
const n = envelopes.length;
envelopes.sort((e1, e2) => {
if (e1[0] - e2[0]) {
return e1[0] - e2[0];
} else {
return e2[1] - e1[1];
}
})
const f = [envelopes[0][1]];
for (let i = 1; i < n; ++i) {
const num = envelopes[i][1];
if (num > f[f.length - 1]) {
f.push(num);
} else {
const index = binarySearch(f, num);
f[index] = num;
}
}
return f.length;
}
const binarySearch = (f, target) => {
let low = 0, high = f.length - 1;
while (low < high) {
const mid = Math.floor((high - low) / 2) + low;
if (f[mid] < target) {
low = mid + 1;
} else {
high = mid;
}
}
return low;
};
python3 解法, 执行用时: 228 ms, 内存消耗: 51.2 MB, 提交时间: 2023-09-24 18:59:23
class Solution:
def maxEnvelopes(self, envelopes: List[List[int]]) -> int:
if not envelopes:
return 0
n = len(envelopes)
envelopes.sort(key=lambda x: (x[0], -x[1]))
f = [envelopes[0][1]]
for i in range(1, n):
if (num := envelopes[i][1]) > f[-1]:
f.append(num)
else:
index = bisect.bisect_left(f, num)
f[index] = num
return len(f)
java 解法, 执行用时: 48 ms, 内存消耗: 92.9 MB, 提交时间: 2023-09-24 18:59:16
class Solution {
public int maxEnvelopes0(int[][] envelopes) {
if (envelopes.length == 0) {
return 0;
}
int n = envelopes.length;
Arrays.sort(envelopes, new Comparator<int[]>() {
public int compare(int[] e1, int[] e2) {
if (e1[0] != e2[0]) {
return e1[0] - e2[0];
} else {
return e2[1] - e1[1];
}
}
});
int[] f = new int[n];
Arrays.fill(f, 1);
int ans = 1;
for (int i = 1; i < n; ++i) {
for (int j = 0; j < i; ++j) {
if (envelopes[j][1] < envelopes[i][1]) {
f[i] = Math.max(f[i], f[j] + 1);
}
}
ans = Math.max(ans, f[i]);
}
return ans;
}
public int maxEnvelopes(int[][] envelopes) {
if (envelopes.length == 0) {
return 0;
}
int n = envelopes.length;
Arrays.sort(envelopes, new Comparator<int[]>() {
public int compare(int[] e1, int[] e2) {
if (e1[0] != e2[0]) {
return e1[0] - e2[0];
} else {
return e2[1] - e1[1];
}
}
});
List<Integer> f = new ArrayList<Integer>();
f.add(envelopes[0][1]);
for (int i = 1; i < n; ++i) {
int num = envelopes[i][1];
if (num > f.get(f.size() - 1)) {
f.add(num);
} else {
int index = binarySearch(f, num);
f.set(index, num);
}
}
return f.size();
}
public int binarySearch(List<Integer> f, int target) {
int low = 0, high = f.size() - 1;
while (low < high) {
int mid = (high - low) / 2 + low;
if (f.get(mid) < target) {
low = mid + 1;
} else {
high = mid;
}
}
return low;
}
}
cpp 解法, 执行用时: 284 ms, 内存消耗: 76 MB, 提交时间: 2023-09-24 18:58:06
class Solution {
public:
// f[i] 表示 h 的前 i 个元素可以组成的最长严格递增子序列的长度，并且我们必须选择第 i 个元素 hi 。
int maxEnvelopes0(vector<vector<int>>& envelopes) {
if (envelopes.empty()) {
return 0;
}
int n = 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> f(n, 1);
for (int i = 1; i < n; ++i) {
for (int j = 0; j < i; ++j) {
if (envelopes[j][1] < envelopes[i][1]) {
f[i] = max(f[i], f[j] + 1);
}
}
}
return *max_element(f.begin(), f.end());
}
// f[j] 表示 h 的前 i 个元素可以组成的长度为 j 的最长严格递增子序列的末尾元素的最小值
int maxEnvelopes(vector<vector<int>>& envelopes) {
if (envelopes.empty()) {
return 0;
}
int n = 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> f = {envelopes[0][1]};
for (int i = 1; i < n; ++i) {
if (int num = envelopes[i][1]; num > f.back()) {
f.push_back(num);
}
else {
auto it = lower_bound(f.begin(), f.end(), num);
*it = num;
}
}
return f.size();
}
};