1035. 不相交的线

🟠   🔖  数组 动态规划  🔗 力扣 LeetCode

题目

You are given two integer arrays nums1 and nums2. We write the integers of nums1 and nums2 (in the order they are given) on two separate horizontal lines.

We may draw connecting lines: a straight line connecting two numbers nums1[i] and nums2[j] such that:

• nums1[i] == nums2[j], and
• the line we draw does not intersect any other connecting (non-horizontal) line.

Note that a connecting line cannot intersect even at the endpoints (i.e., each number can only belong to one connecting line).

Return the maximum number of connecting lines we can draw in this way.

Example 1:

Input: nums1 = [1,4,2], nums2 = [1,2,4]

Output: 2

Explanation: We can draw 2 uncrossed lines as in the diagram.

We cannot draw 3 uncrossed lines, because the line from nums1[1] = 4 to nums2[2] = 4 will intersect the line from nums1[2]=2 to nums2[1]=2.

Example 2:

Input: nums1 = [2,5,1,2,5], nums2 = [10,5,2,1,5,2]

Output: 3

Example 3:

Input: nums1 = [1,3,7,1,7,5], nums2 = [1,9,2,5,1]

Output: 2

Constraints:

• 1 <= nums1.length, nums2.length <= 500
• 1 <= nums1[i], nums2[j] <= 2000

题目大意

在两条独立的水平线上按给定的顺序写下 nums1 和 nums2 中的整数。

现在，可以绘制一些连接两个数字 nums1[i] 和 nums2[j] 的直线，这些直线需要同时满足：

• nums1[i] == nums2[j]
• 且绘制的直线不与任何其他连线（非水平线）相交。

请注意，连线即使在端点也不能相交：每个数字只能属于一条连线。

以这种方法绘制线条，并返回可以绘制的最大连线数。

示例 1：

输入： nums1 = [1,4,2], nums2 = [1,2,4]

输出： 2

解释： 可以画出两条不交叉的线，如上图所示。

但无法画出第三条不相交的直线，因为从 nums1[1]=4 到 nums2[2]=4 的直线将与从 nums1[2]=2 到 nums2[1]=2 的直线相交。

示例 2：

输入： nums1 = [2,5,1,2,5], nums2 = [10,5,2,1,5,2]

输出： 3

示例 3：

输入： nums1 = [1,3,7,1,7,5], nums2 = [1,9,2,5,1]

输出： 2

提示：

• 1 <= nums1.length, nums2.length <= 500
• 1 <= nums1[i], nums2[j] <= 2000

解题思路

题目要求找到不相交的最大连线数，可以看作在两个数组 nums1 和 nums2 之间找到最长公共子序列 (LCS)。

1. 关键思路

   • 如果 nums1[i] == nums2[j]，则可以连接这两个元素，并加上它们前面的最长连线数 dp[i-1][j-1] + 1。
   • 否则，nums1[i] 和 nums2[j] 不能连接，我们取两种可能情况的最大值：
     • dp[i-1][j]（不使用 nums1[i]）
     • dp[i][j-1]（不使用 nums2[j]）

2. 状态定义 设 dp[i][j] 表示在 nums1[0...i-1] 和 nums2[0...j-1] 之间的最大连线数。

3. 状态转移方程

   • 如果当前元素相等 (nums1[i-1] == nums2[j-1])：

     dp[i][j] = dp[i-1][j-1] + 1

   • 否则，不连这两个元素，取前面的最大值：

     dp[i][j] = max(dp[i-1][j], dp[i][j-1])

4. 初始化

   • dp[0][j] = 0，dp[i][0] = 0，因为任何一个数组为空时，最长连线数都是 0。

5. 优化

   • dp[i][j] 只依赖于 dp[i-1][j]、dp[i][j-1] 和 dp[i-1][j-1]，我们可以用滚动数组优化空间到 O(m)（只存储两行）。

复杂度分析

• 时间复杂度: O(n * m)，两层循环。
• 空间复杂度: O(n * m)，存储 dp 数组。
  • dp[i][j] 只依赖于 dp[i-1][j]、dp[i][j-1] 和 dp[i-1][j-1]，只用到前一行和当前行。
  • 因此，可以用两个一维数组来代替 O(n * m) 的 dp 数组，把空间优化到 O(m)。

代码

动态规划

/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @return {number}
 */
var maxUncrossedLines = function (nums1, nums2) {
	const n = nums1.length;
	const m = nums2.length;
	const dp = new Array(n + 1).fill().map(() => new Array(m + 1).fill(0));
	for (let i = 1; i <= n; i++) {
		for (let j = 1; j <= m; j++) {
			dp[i][j] = Math.max(dp[i][j - 1], dp[i - 1][j]);
			if (nums1[i - 1] == nums2[j - 1]) {
				dp[i][j] = Math.max(1 + dp[i - 1][j - 1], dp[i][j]);
			}
		}
	}
	return dp[n][m];
};

动态规划-滚动数组

/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @return {number}
 */
var maxUncrossedLines = function (nums1, nums2) {
	const n = nums1.length,
		m = nums2.length;
	let prev = new Array(m + 1).fill(0);
	let curr = new Array(m + 1).fill(0);

	for (let i = 1; i <= n; i++) {
		for (let j = 1; j <= m; j++) {
			curr[j] = Math.max(curr[j - 1], prev[j]);
			if (nums1[i - 1] === nums2[j - 1]) {
				curr[j] = Math.max(curr[j], prev[j - 1] + 1);
			}
		}
		[prev, curr] = [curr, prev]; // 交换数组，节省空间
	}
	return prev[m];
};

相关题目

题号	标题	题解	标签	难度	力扣
72	编辑距离	[✓]	字符串 动态规划	🟠	🀄️ 🔗