代码拉取完成,页面将自动刷新
同步操作将从 doocs/leetcode 强制同步,此操作会覆盖自 Fork 仓库以来所做的任何修改,且无法恢复!!!
确定后同步将在后台操作,完成时将刷新页面,请耐心等待。
给你一个二维整数数组 envelopes
,其中 envelopes[i] = [wi, hi]
,表示第 i
个信封的宽度和高度。
当另一个信封的宽度和高度都比这个信封大的时候,这个信封就可以放进另一个信封里,如同俄罗斯套娃一样。
请计算 最多能有多少个 信封能组成一组“俄罗斯套娃”信封(即可以把一个信封放到另一个信封里面)。
注意:不允许旋转信封。
示例 1:
3, 组合为:
示例 2:
输入:envelopes = [[1,1],[1,1],[1,1]] 输出:1
提示:
1 <= envelopes.length <= 105
envelopes[i].length == 2
1 <= wi, hi <= 105
按 w 进行升序排序,若 w 相同则按 h 降序排序。然后问题转换为求 h 数组的最长递增子序列长度。参考 300. 最长递增子序列。
方法一:贪心 + 二分查找
时间复杂度 O(nlogn)。
class Solution:
def maxEnvelopes(self, envelopes: List[List[int]]) -> int:
envelopes.sort(key=lambda x: (x[0], -x[1]))
d = [envelopes[0][1]]
for _, h in envelopes[1:]:
if h > d[-1]:
d.append(h)
else:
idx = bisect_left(d, h)
if idx == len(d):
idx = 0
d[idx] = h
return len(d)
class Solution {
public int maxEnvelopes(int[][] envelopes) {
Arrays.sort(envelopes, (a, b) -> { return a[0] == b[0] ? b[1] - a[1] : a[0] - b[0]; });
int n = envelopes.length;
int[] d = new int[n + 1];
d[1] = envelopes[0][1];
int size = 1;
for (int i = 1; i < n; ++i) {
int x = envelopes[i][1];
if (x > d[size]) {
d[++size] = x;
} else {
int left = 1, right = size;
while (left < right) {
int mid = (left + right) >> 1;
if (d[mid] >= x) {
right = mid;
} else {
left = mid + 1;
}
}
int p = d[left] >= x ? left : 1;
d[p] = x;
}
}
return size;
}
}
class Solution {
public:
int maxEnvelopes(vector<vector<int>>& envelopes) {
sort(envelopes.begin(), envelopes.end(), [](const auto& e1, const auto& e2) {
return e1[0] < e2[0] || (e1[0] == e2[0] && e1[1] > e2[1]);
});
int n = envelopes.size();
vector<int> d {envelopes[0][1]};
for (int i = 1; i < n; ++i) {
int x = envelopes[i][1];
if (x > d[d.size() - 1])
d.push_back(x);
else {
int idx = lower_bound(d.begin(), d.end(), x) - d.begin();
if (idx == d.size()) idx = 0;
d[idx] = x;
}
}
return d.size();
}
};
func maxEnvelopes(envelopes [][]int) int {
sort.Slice(envelopes, func(i, j int) bool {
if envelopes[i][0] != envelopes[j][0] {
return envelopes[i][0] < envelopes[j][0]
}
return envelopes[j][1] < envelopes[i][1]
})
n := len(envelopes)
d := make([]int, n+1)
d[1] = envelopes[0][1]
size := 1
for _, e := range envelopes[1:] {
x := e[1]
if x > d[size] {
size++
d[size] = x
} else {
left, right := 1, size
for left < right {
mid := (left + right) >> 1
if d[mid] >= x {
right = mid
} else {
left = mid + 1
}
}
if d[left] < x {
left = 1
}
d[left] = x
}
}
return size
}
此处可能存在不合适展示的内容,页面不予展示。您可通过相关编辑功能自查并修改。
如您确认内容无涉及 不当用语 / 纯广告导流 / 暴力 / 低俗色情 / 侵权 / 盗版 / 虚假 / 无价值内容或违法国家有关法律法规的内容,可点击提交进行申诉,我们将尽快为您处理。