1035. Uncrossed Lines

题目信息

题号:

1035

难度:

Medium

主题:

两个数组、相等元素配对、不交叉连线

原题:

LeetCode 1035

重点:

只能连接值相等的元素,每个下标最多使用一次;所选配对在两个数组中的下标顺序必须一致,避免连线相交

题目重述

把数组 nums1 和 nums2 分别水平排列。可以在两个数组之间画线,每条线连接一个 nums1[i] 与一个值相等的 nums2[j]。

同一个数组元素不能连接多次,并且任意两条线不能在内部相交。等价地,若选择了配对 (i1, j1) 和 (i2, j2) 且 i1 < i2,就必须满足 j1 < j2。请返回最多可以画出的线数量。

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

自建示例

数值相等但顺序冲突的连接不能同时选择:

输入:nums1 = [1,3,2,4], nums2 = [3,1,4,2]
输出:2
解释:可以连接 1 与 1、2 与 2,或者连接 3 与 3、4 与 4;无法同时选择三条而保持两侧下标顺序一致。

两个数组没有共同值:

输入:nums1 = [1,2], nums2 = [3,4]
输出:0
解释:不存在值相等的元素对,因此一条线也无法画出。