354. 俄罗斯套娃信封问题

🔴   🔖  数组 二分查找 动态规划 排序  🔗 力扣 LeetCode

题目

You are given a 2D array of integers envelopes where envelopes[i] = [wi, hi] represents the width and the height of an envelope.

One envelope can fit into another if and only if both the width and height of one envelope are greater than the other envelope's width and height.

Return the maximum number of envelopes you can Russian doll (i.e., put one inside the other).

Note: You cannot rotate an envelope.

Example 1:

Input: envelopes = [[5,4],[6,4],[6,7],[2,3]]

Output: 3

Explanation: The maximum number of envelopes you can Russian doll is 3 ([2,3] => [5,4] => [6,7]).

Example 2:

Input: envelopes = [[1,1],[1,1],[1,1]]

Output: 1

Constraints:

• 1 <= envelopes.length <= 10^5
• envelopes[i].length == 2
• 1 <= wi, hi <= 10^5

题目大意

给你一个二维整数数组 envelopes ，其中 envelopes[i] = [wi, hi] ，表示第 i 个信封的宽度和高度。

当另一个信封的宽度和高度都比这个信封大的时候，这个信封就可以放进另一个信封里，如同俄罗斯套娃一样。

请计算 最多能有多少个 信封能组成一组“俄罗斯套娃”信封（即可以把一个信封放到另一个信封里面）。

注意：不允许旋转信封。

解题思路

1. 排序：

   • 先按 宽度 w 升序 排序。
   • 若 w 相同，则按 h 降序 排序，避免相同 w 的情况下错误嵌套。

2. 在高度 h 序列上求 LIS：

   • 由于 w 递增，我们只需在 h 维度上找到 最长递增子序列（LIS）。
   • 采用 贪心 + 二分查找 的方式来求 LIS，使用 tails 数组：
     • tails[i] 代表长度为 i+1 的 LIS 的最小结尾元素。
     • 通过 二分查找 维护 tails，最终 tails 的长度就是 LIS 长度。

复杂度分析

• 时间复杂度：O(n log n)，其中 n 是信封的数量。对信封数组进行排序的时间复杂度为 O(n log n)；在排好序的信封数组中，使用二分查找求最长递增子序列的时间复杂度为 O(n log n)。
• 空间复杂度：O(n)，需要额外的空间来存储高度的数组和辅助数组。

代码

/**
 * @param {number[][]} envelopes
 * @return {number}
 */
var maxEnvelopes = function (envelopes) {
	envelopes.sort((a, b) => (a[0] == b[0] ? b[1] - a[1] : a[0] - b[0]));
	const heights = envelopes.map((i) => i[1]);
	return heightsOfLIS(heights);
};

// 求最长递增子序列（LIS）
var heightsOfLIS = function (heights) {
	let tails = [];
	let len = 0;
	for (let i = 0; i < heights.length; i++) {
		let left = 0;
		let right = len;
		while (left < right) {
			const mid = ((left + right) / 2) | 0;
			if (tails[mid] < heights[i]) {
				left = mid + 1;
			} else {
				right = mid;
			}
		}
		if (left === len) {
			tails[len++] = heights[i];
		} else {
			tails[left] = heights[i];
		}
	}
	return len;
};

相关题目

题号	标题	题解	标签	难度	力扣
300	最长递增子序列	[✓]	数组 二分查找 动态规划	🟠	🀄️ 🔗
1996	游戏中弱角色的数量		栈 贪心 数组 2+	🟠	🀄️ 🔗
2771	构造最长非递减子数组		数组 动态规划	🟠	🀄️ 🔗