LeetCode 1035. 不相交的线

2026-03-17 HGNULB 约 9 分钟

文章信息 8 个分类 4 个标签

分类

题目描述

✅ 1035. 不相交的线

题意分析

两个整数数组分别写在上下两行，位置固定、顺序不能调整。允许在上行的某个数和下行的某个相等的数之间画一条直线，要求任意两条线不能交叉，且每个位置最多参与一条线。问最多能画多少条。

「不相交」这个几何条件其实是一个纯粹的顺序条件。设两条线分别连接上行下标 i1、i2 与下行下标 j1、j2，若 i1 < i2，那么必须有 j1 < j2，否则两条线一定会在中间某处穿过。所以所有被画出的线，其上行下标和下行下标的排列顺序必须完全一致。

「每个数字最多属于一条连线」则保证了这些下标各不重复。把这两条合起来看，被选中的连线集合等价于：从上行取一个下标严格递增的子序列，从下行取一个等长且下标严格递增的子序列，两者逐位数值相等。

约束规模上，两个数组长度都不超过五百，元素值域也很小，所以平方级别的做法完全够用，不需要追求更优。

边界要注意：数组长度至少为 1；两数组可能毫无公共元素，答案是 0；数组内可以有重复值，同一个数字在两行里出现多次时，选哪一次会影响后续的可用范围。

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

核心思路

暴力枚举很直接：枚举上行的所有子序列，再在下行找能与之匹配的等值同序子序列。上行子序列有 $2^m$ 个，完全不可行。瓶颈在于子序列之间共享了大量结构——两个子序列如果只有最后一位不同，前面那段的匹配情况其实是同一个问题。

于是转向按前缀分解。观察最后一条线可能的样子：考虑 nums1 的前 i 个数和 nums2 的前 j 个数，最优方案里 nums1[i-1] 和 nums2[j-1] 这两个末位元素只有三种命运。要么它们互相连线（这只有在两者相等时可能，此时剩下的问题变成前 i-1 和前 j-1）；要么 nums1[i-1] 没参与任何线（问题退化成前 i-1 和前 j）；要么 nums2[j-1] 没参与（退化成前 i 和前 j-1）。三种情况覆盖完全，取最大即可。

状态定义：dp[i][j] 表示只看 nums1 的前 i 个元素与 nums2 的前 j 个元素时，能画出的最大连线数。 转移是：若 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])。边界是 dp[0][j] = dp[i][0] = 0，因为任一侧为空就画不出线。答案是 dp[m][n]。

这正是最长公共子序列的递推式，本题只是换了一层几何外衣。

再看空间。转移只依赖上一行和当前行左侧，所以二维表可以压成一维。压缩后 dp[j] 在被覆盖之前存的是上一行的值（即 dp[i-1][j]），覆盖之后存的是当前行的值（即 dp[i][j]）。麻烦的是相等分支要用的 dp[i-1][j-1]：走到 j 时 dp[j-1] 已经被本行覆盖过了，旧值丢失。所以额外用一个 prev 变量把「上一轮循环开始前的 dp[j]」保存下来，它恰好就是下一轮需要的左上角。滚动数组下的不变量是：内层循环处理下标 j 时，dp[j] 尚未更新故等于 dp[i-1][j]，dp[j-1] 已更新故等于 dp[i][j-1]，而 prev 等于 dp[i-1][j-1]。

解题步骤

开一个长度为 nums2.length + 1 的数组 dp，初值全为 0。多出来的第 0 位代表「nums2 取空前缀」，让边界不必特判。

外层循环 i 从 1 到 nums1.length，代表逐步扩大 nums1 的前缀。每进入新的一行，先把 prev 重置为 0，因为 dp[i-1][0] 恒为 0。这次重置不能漏，否则左上角会串到上一行的残留值。

内层循环 j 从 1 到 nums2.length。进入循环体的第一件事是 temp = dp[j]，把尚未覆盖的旧值（也就是上一行同列的值）先存起来，它将在下一轮充当左上角。

若 nums1[i-1] == nums2[j-1]，令 dp[j] = prev + 1。含义是这两个末位元素配成一条线，加上它们各自之前那段的最优解。注意用的是 prev 而不是 dp[j-1]，前者才是真正的左上角。

否则令 dp[j] = max(dp[j], dp[j-1])。此时 dp[j] 还是上一行的值（放弃 nums1[i-1]），dp[j-1] 是本行左侧的值（放弃 nums2[j-1]），两者取大。

循环体末尾执行 prev = temp，把刚保存的旧值交给下一列使用。

全部跑完后返回 dp[nums2.length]，即 dp[m][n]。

以 nums1 = [1,4,2]、nums2 = [1,2,4] 走一遍：dp 初始为 [0,0,0,0]。第一行 i = 1，对应 nums1[0] = 1，prev 置 0。j = 1：temp = 0，nums2[0] = 1 与之相等，dp[1] = prev + 1 = 1，prev 更新为 0。j = 2：temp = 0，nums2[1] = 2 不等，dp[2] = max(0, dp[1] = 1) = 1，prev 为 0。j = 3：temp = 0，nums2[2] = 4 不等，dp[3] = max(0, dp[2] = 1) = 1，prev 为 0。此时 dp 是 [0,1,1,1]。第二行 i = 2，对应 nums1[1] = 4，prev 重置为 0。j = 1：temp = 1，1 != 4，dp[1] = max(1, dp[0] = 0) = 1，prev 变 1。j = 2：temp = 1，2 != 4，dp[2] = max(1, dp[1] = 1) = 1，prev 变 1。j = 3：temp = 1，4 == 4，dp[3] = prev + 1 = 2，prev 变 1。此时 dp 是 [0,1,1,2]。第三行 i = 3，对应 nums1[2] = 2，prev 重置为 0。j = 1：temp = 1，1 != 2，dp[1] = max(1, 0) = 1，prev 变 1。j = 2：temp = 1，2 == 2，dp[2] = prev + 1 = 2，prev 变 1。j = 3：temp = 2，4 != 2，dp[3] = max(2, dp[2] = 2) = 2，prev 变 2。最终 dp 是 [0,1,2,2]，返回 dp[3] = 2。对应的画法是连 1 与 1、连 4 与 4（或连 1 与 1、连 2 与 2），两条线都不交叉。

代码实现

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)$，滚动数组只保留一行长度为 $n + 1$ 的表，外加 prev、temp 两个标量；相比朴素二维表的 $O(mn)$ 少了一个维度。

关键点总结

几何约束经常可以翻译成顺序约束。看到「不相交」「不重叠」「按序对应」这类描述，先尝试写出下标之间的不等式，往往就能识破它其实是某个经典序列模型。

双序列动态规划的通用套路是「看两个末位元素的三种命运」：配对、丢弃左边、丢弃右边。把这三种情形写全，转移方程自然浮现，不需要死记。

状态里用「前 i 个」而不是「下标 i」，可以把空前缀这个边界自然收进 dp[0][*]，省掉一圈特判，代价只是数组多开一格、访问原数组时减一。

滚动数组压缩的关键是搞清楚每个位置在被覆盖前后分别代表哪一行。凡是转移用到左上角的，都必须额外用一个变量把旧值截留下来，这是压缩类题目的固定动作。

面试视角：这题的价值在于「识别」。能一句话说清「不相交等价于保序，因此答案就是最长公共子序列」，比写出转移方程更重要，也是面试官真正想听的那句。

面试视角：常见追问是「如果要输出具体连了哪些线呢」。答案是必须保留二维表，从 dp[m][n] 回溯：相等且值来自左上角加一就记录一条线，否则往取大的那一侧走。这时空间就不能压缩了，这个取舍值得主动说出来。

易错点总结

错误写法：把问题当成最长公共子串，要求匹配元素连续，转移写成不相等时置 0。用例 nums1 = [1,4,2]、nums2 = [1,2,4] → 只能得到长度 1，而正确答案是 2，因为连线只要求保序不要求相邻。

错误写法：滚动数组里相等分支直接写 dp[j] = dp[j-1] + 1。用例 nums1 = [2]、nums2 = [2,2] → dp[1] 被本行更新为 1 后，j = 2 又拿它加一得到 dp[2] = 2，等于让同一个 2 连了两条线，正确答案只有 1。

错误写法：把 prev 定义在外层循环之外，每行开始时不重置为 0。用例 nums1 = [5,9,5]、nums2 = [5,1] → 第三行开头会拿第二行末尾残留的 prev = 1 当左上角，算出 dp[1] = 2，最终返回 2，而正确答案是 1。

错误写法：把 prev = temp 写在 if 分支内部而不是循环体末尾。用例任意含不等元素的输入 → 走不相等分支时 prev 不更新，下一列拿到的是过期的左上角，结果偏大或偏小。

错误写法：temp = dp[j] 放在更新 dp[j] 之后。用例 nums1 = [1,4,2]、nums2 = [1,2,4] → 存下来的是当前行的新值而非上一行的旧值，左上角语义彻底错乱。

错误写法：dp 数组只开 nums2.length 长且下标从 0 用起。用例 nums1 = [1]、nums2 = [1] → 访问 dp[j-1] 时 j = 0 直接越界，或者被迫为首行首列写一堆特判。

错误写法：不相等分支写成 dp[j] = dp[j-1]，漏掉与上一行的比较。用例 nums1 = [1,2]、nums2 = [1,3] → 第二行 j = 2 会把 dp[2] 覆盖成 dp[1]，丢掉上一行已经攒下的连线数，答案偏小。

错误写法：认为数组元素互不相同，于是用哈希表记录 nums2 中每个值的唯一位置，再求位置序列的最长递增子序列。用例 nums1 = [2,5,1,2,5]、nums2 = [10,5,2,1,5,2] → 存在重复值时一个数字对应多个位置，单一映射会丢掉更优的配对方案。

错误写法：最后返回 dp[nums1.length] 或返回内层循环里记录的最大值。用例 nums1 = [1,3,7,1,7,5]、nums2 = [1,9,2,5,1] → dp 只有 6 个位置而 nums1.length 是 6，下标 6 直接越界；即使两数组长度相近不越界，读到的也是中间某列的值，而答案必须取两个数组都用满时的那一格。

相似题目

题目	难度	考察点
1143. 最长公共子序列	中等	本题去掉几何外衣后的原型，转移方程完全一致
LCR 095. 最长公共子序列	中等	同一模型的国内版编号，可用来验证模板稳定性
718. 最长重复子数组	中等	要求匹配段连续，不相等时状态必须归零
72. 编辑距离	中等	三种操作对应三条转移，求最小代价而非最大长度
583. 两个字符串的删除操作	中等	求最少删除次数，可由公共子序列长度反推
712. 两个字符串的最小ASCII删除和	中等	代价按字符权重计算，不能简单套用长度模型
97. 交错字符串	中等	状态存布尔可行性，两串必须完整用尽
LCR 096. 交错字符串	中等	同上题模型，适合对比滚动数组的写法差异
516. 最长回文子序列	中等	单串与自身逆序求公共子序列，或改用区间 DP