【每日一题】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)\)）
- 遍历 arrays 记录当前最大值和最小值分别为 min_n 和 max_n，初始化为第一个 array 的最大值和最小值，同时初始化 distance 为 0 （由于必定有答案且为绝对值，所以初始化为 0 ）。
- 根据贪心，计算当前 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博客！
文章评论