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 个信封的宽度和高度。

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

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

注意：不允许旋转信封。

解题思路

这个问题可以转化为求一组数对的最长链问题。首先对信封按照宽度进行排序，如果宽度相同，则按高度递减排序。然后，可以将问题转化为找出最长的严格递增子序列（LIS）。

1. 排序：

   • 首先对信封按照宽度进行升序排序。
   • 如果宽度相同，则按高度递减排序，这样可以避免宽度相同的信封之间互相套娃。

2. 动态规划求解最长递增子序列：

   • 初始化左右指针：left 指向 0，right 指向 len。

   • 开始二分查找：

     • 在当前的辅助数组 tails 中进行二分查找，找到第一个大于等于 nums[i] 的位置。用 mid 表示二分查找中间位置。
     • 如果 tails[mid] < nums[i]，说明当前的递增子序列可以继续延长，因此更新 left = mid + 1。
     • 否则，说明当前递增子序列需要进行调整，因此更新 right = mid。

   • 更新辅助数组：

     • 如果 left === len，说明 nums[i] 大于当前递增子序列的所有元素，将 nums[i] 添加到辅助数组的末尾，并且递增子序列的长度 len++。
     • 否则，将 nums[i] 替换掉辅助数组中第一个大于等于 nums[i] 的元素。

   • 迭代下一个元素：重复上述过程，直到遍历完整个数组 nums。

   • 最终结果：辅助数组的长度 len 即为最长递增子序列的长度。

复杂度分析

• 时间复杂度：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) => {
		if (a[0] == b[0]) {
			return b[1] - a[1];
		} else {
			return a[0] - b[0];
		}
	});
	const height = envelopes.map((i) => i[1]);
	const tails = [];
	let len = 0;

	for (let i = 0; i < height.length; i++) {
		let left = 0;
		let right = len;

		while (left < right) {
			const mid = Math.floor((left + right) / 2);
			if (tails[mid] < height[i]) {
				left = mid + 1;
			} else {
				right = mid;
			}
		}

		if (left == len) {
			tails[len++] = height[i];
		} else {
			tails[left] = height[i];
		}
	}

	return len;
};

相关题目

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