LeetCode 1035. 不相交的线

2026-03-17 HGNULB 约 5 分钟

文章信息 8 个分类 · 2 个标签

分类

LeetCode CodeTop 中等 未解决 2-5 字节 阿里 微软

标签

数组 动态规划

题目描述

✅ 1035. 不相交的线

题意分析

在两个数组的相等元素之间连线，每个位置最多连接一次，要求连线之间不能相交，求最多能画多少条。可以跳过任意位置，不要求被选中的元素连续。

两条线若在一侧从左到右排列，在另一侧也必须保持相同顺序，否则就会交叉。因此合法连线对应两边按下标递增选出的相同序列，最大连线数就是最长公共子序列的长度。

解法：最长公共子序列动态规划

核心思路

[!blue]

先定义二维状态：D[i][j] 表示第一个数组前 i 个元素与第二个数组前 j 个元素的最大连线数。任意一侧前缀为空，都无法连线，所以第零行和第零列均为 0。

如果两段前缀的最后一个值相同，可以把这两个末端连起来，再接上前面两段的最优结果，得到 D[i - 1][j - 1] + 1。这不会漏掉更优方案：两个末端分别连向对方更早的位置会相交；若只使用了其中一个末端，可以把它的连线改为连接这两个相等末端，不减少条数。

如果末位不同，它们不能直接相连，而同时各自连向对方更早的位置又会交叉，所以至少有一侧的末位不参与。分别考虑跳过第一个数组末位、跳过第二个数组末位，取 D[i - 1][j] 与 D[i][j - 1] 的较大值。

每个状态只依赖上一行和本行左侧，可以把表压成一行。处理第 i 行、第 j 列时，尚未覆盖的 dp[j] 是上一行同列，已经更新的 dp[j - 1] 是本行左侧，另用 prev 保存上一行左上角。

更新前先用 temp 保存旧 dp[j]；相等时读 prev + 1，否则取 dp[j] 与 dp[j - 1] 的较大值。随后令 prev = temp，使下一列仍能读到旧行的左上角。每行开始时 prev = 0，对应上一行的空前缀状态，最终最后一列就是两数组的答案。

解题步骤

1. 创建长度为第二个数组长度加一的 dp，初始全为零。
2. 依次处理第一个数组的元素，每行开始令 prev = 0。
3. 从左到右枚举第二个数组的元素，先保存 temp = dp[j]。
4. 两个当前值相等时令 dp[j] = prev + 1，否则取上一行同列与本行左列的较大值。
5. 更新 prev = temp，继续下一列；全部处理后返回末列值。

代码实现

class Solution {
    public int maxUncrossedLines(int[] nums1, int[] nums2) {
        int[] dp = new int[nums2.length + 1];

        for (int i = 1; i <= nums1.length; i++) {
            // 新行的左上角从空前缀状态零开始。
            int prev = 0;

            for (int j = 1; j <= nums2.length; j++) {
                // 覆盖前保留上一行同列，供下一列充当左上角。
                int temp = dp[j];

                if (nums1[i - 1] == nums2[j - 1]) {
                    dp[j] = prev + 1;
                } else {
                    dp[j] = Math.max(dp[j], dp[j - 1]);
                }

                // 必须传递旧行状态，不能传递刚更新的新值。
                prev = temp;
            }
        }

        return dp[nums2.length];
    }
}

func maxUncrossedLines(nums1 []int, nums2 []int) int {
    dp := make([]int, len(nums2)+1)
    for i := 1; i <= len(nums1); i++ {
        // 新行的左上角从空前缀状态零开始。
        prev := 0
        for j := 1; j <= len(nums2); j++ {
            // 覆盖前保留上一行同列，供下一列充当左上角。
            temp := dp[j]
            if nums1[i-1] == nums2[j-1] {
                dp[j] = prev + 1
            } else if dp[j-1] > dp[j] {
                dp[j] = dp[j-1]
            }
            // 必须传递旧行状态，不能传递刚更新的新值。
            prev = temp
        }
    }
    return dp[len(nums2)]
}

复杂度分析

• 时间复杂度：$O(mn)$，m、n 分别为两个数组长度，每对前缀状态只计算一次。
• 空间复杂度：$O(n + 1)$，只保存第二个数组对应的一行状态及固定数量的临时变量。

关键点总结

[!green]

• 三个来源分属新旧行，解释变量时必须区分时刻。
• 相等时连末位不会少于跳过末位的最优结果。

易错点总结

[!yellow]

• 相等时读取本行左侧再加一：可能在一行里重复使用第一个数组的同一个元素，必须读取旧行左上角。
• 覆盖后才保存 dp[j]：会把新行状态当成下一列的左上角，应先备份旧值。
• 每行不重置 prev：会混入上一行末尾的状态，而不是正确的空前缀状态。
• 不相等时清零：本题允许跳过元素，应继承两侧较大值，不能当作连续公共子数组处理。

相似题目

题目	难度	关联与区别
1143. 最长公共子序列	中等	不相交匹配线等价于保持两侧下标顺序的公共子序列，因此可直接转成LCS。
718. 最长重复子数组	中等	原题要求连续公共片段，本题可以不连接某些位置，所以应使用子序列状态。

转载与许可

作者 HGNULB

链接 https://hgnulb.github.io/blog/2026/46471355

许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！