数组列表中的最大距离

题目表述

给定 m 个数组，每个数组都已经按照升序排好序了。现在你需要从两个不同的数组中选择两个整数（每个数组选一个）并且计算它们的距离。两个整数 a 和 b 之间的距离定义为它们差的绝对值 |a-b| 。你的任务就是去找到最大距离

示例 1

输入：

[[1,2,3], [4,5], [1,2,3]]

输出： 4

解释：一种得到答案 4 的方法是从第一个数组或者第三个数组中选择 1，同时从第二个数组中选择 5 。

提示

每个给定数组至少会有 1 个数字。列表中至少有两个非空数组。

所有 m 个数组中的数字总数目在范围 [2, 10000] 内。

m 个数组中所有整数的范围在 [-10000, 10000] 内。

解法一：遍历

一次遍历，记录数组的最大值和最小值，由于最大最小值不能在同一个数组中，因此需要唯一一份次大值次小值

代码实现

from typing import List


class Solution:
    """
    一次遍历记录数组最大最小值，为了防止最大最小值在同一个数组中，需要记录不同数组的次大值、次小值
    """

    def maxDistance(self, arrays: List[List[int]]) -> int:
        # 依次记录最大值，数组索引，次大值，数组索引
        max1 = imax1 = max2 = imax2 = None
        min1 = imin1 = min2 = imin2 = None
        for i, arr in enumerate(arrays):
            # 求数组最大最小值
            arr_min = arr_max = arr[0]
            for v in arr:
                arr_max = max(arr_max, v)
                arr_min = min(arr_min, v)
            if i == 0:
                max1, imax1 = arr_max, i
                min1, imin1 = arr_min, i
            elif i == 1:
                max2, imax2 = arr_max, i
                min2, imin2 = arr_min, i
                if max1 < max2:
                    max1, imax1, max2, imax2 = max2, imax2, max1, imax1
                if min1 > min2:
                    min1, imin1, min2, imin2 = min2, imin2, min1, imin1
            else:
                if arr_max > max1:
                    max1, imax1, max2, imax2 = arr_max, i, max1, imax1
                elif arr_max > max2:
                    max2, imax2 = arr_max, i
                if arr_min < min1:
                    min1, imin1, min2, imin2 = arr_min, i, min1, imin1
                elif arr_min < min2:
                    min2, imin2 = arr_min, i
        # 返回最终结果，需要判断是否在同一个数组中
        if imax1 != imin1:
            return max1 - min1
        return max(max1 - min2, max2 - min1)


if __name__ == "__main__":
    arrs = [[-1, 1], [-3, 1, 4], [-2, -1, 0, 2]]
    res = Solution().maxDistance(arrs)
    print(res, res == 6)
    arrs = [[1, 4], [0, 5]]
    res = Solution().maxDistance(arrs)
    print(res, res == 4)

// 略