【每日一题】Leetcode 624. 数组列表中的最大距离

【每日一题】Leetcode 624. 数组列表中的最大距离

——跳转原题

给定 m 个数组，每个数组都已经按照升序排好序了。

现在你需要从两个不同的数组中选择两个整数（每个数组选一个）并且计算它们的距离。两个整数 a 和 b 之间的距离定义为它们差的绝对值 |a-b| 。

返回最大距离。

示例 1：

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

示例 2：

输入：arrays = [[1],[1]]
输出：0

提示 ：

m == arrays.length
2 <= m <= 10^5
1 <= arrays[i].length <= 500
-10^4 <= arrays[i][j] <= 10^4
arrays[i] 以 升序 排序。
所有数组中最多有 10^5 个整数。

思路 1：（时间复杂度$O(n)$）

1. 遍历 arrays 记录当前最大值和最小值分别为 min_n 和 max_n，初始化为第一个 array 的最大值和最小值，同时初始化 distance 为 0 （由于必定有答案且为绝对值，所以初始化为 0 ）。
2. 根据贪心，计算当前 array 中最小值 array[0] 与最大值 max_n 之间的距离，以及最大值 array[-1] 与 min_n 之间的距离，记录它们之间的最大值，再比较上一个记录的 distance。

代码 1：

class Solution:
    def maxDistance(self, arrays: List[List[int]]) -> int:
        min_n = arrays[0][0] # array 有序
        max_n = arrays[0][-1] # array 有序
        distance = 0
        for array in arrays[1:]:
            distance = max(max(abs(array[0] - max_n), abs(array[-1] - min_n)), distance)
            min_n = min(array[0], min_n)
            max_n = max(array[-1], max_n)

        return distance

感谢浏览，欢迎关注祁彧w博客！