本题解的思路是将问题转化为寻找两个数组之间的最长递增子序列（Longest Increasing Subsequence, LIS）的问题。首先，为了方便处理，确保nums1是两个数组中较短的一个。然后，使用一个字典dic来存储nums1中每个数字的所有出现位置，并按照逆序存储，以便后续操作。接下来，遍历nums2数组，将nums2中的元素按照在nums1中出现的位置顺序记录到一个列表tmp中。这一步是为了找到所有在nums1和nums2中都出现的元素，并保留其在nums1中的位置。最后，通过计算tmp列表的最长递增子序列的长度来确定最大的不相交的线的数量，这是因为这些位置的递增序列对应于不相交的连接线。
时间复杂度: O(m log m)
空间复杂度: O(n + m)
#class Solution:
# def maxUncrossedLines(self, nums1: List[int], nums2: List[int]) -> int:
# nums2 = nums2[::-1]
# @cache
# def find(n, m):
# if not n or m == len(nums2): return 0
# try: return max(find(n - 1, nums2[m:].index(nums1[n - 1]) + m + 1) + 1, find(n - 1, m))
# except: return find(n - 1, m)
# return find(len(nums1), 0)
class Solution:
def maxUncrossedLines(self, nums1: List[int], nums2: List[int]) -> int:
# 选择较短的数组作为nums1以减少空间使用
nums1, nums2 = (nums2, nums1) if len(nums2) > len(nums1) else (nums1, nums2)
# 创建字典存储nums1中元素的索引，逆序存储以便后续操作
dic = collections.defaultdict(list)
for i in range(len(nums1) - 1, -1, -1):
dic[nums1[i]].append(i)
# 遍历nums2，记录nums1中元素的出现位置
tmp = []
for n in nums2:
tmp += dic[n]
# 使用二分法计算最长递增子序列
dp = []
for x in tmp:
i = bisect_left(dp, x)
if i == len(dp): dp.append(x)
else: dp[i] = x
# 返回最长递增子序列的长度，即最大连线数
return len(dp)
