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