Solutions CS101

Appearance

624.数组列表中的最大距离 ​

greedy, https://leetcode.cn/problems/maximum-distance-in-arrays/

给定 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
  • -104 <= arrays[i][j] <= 10^4
  • arrays[i] 以 升序 排序。
  • 所有数组中最多有 10^5 个整数。

为了解决这个问题，我们需要找到来自不同数组的两个数，使得它们之间的差的绝对值最大。直接比较所有可能的组合会非常低效，因此我们需要一种更高效的方法来确定最大距离。

考虑到每个数组都是排序好的，我们可以利用这一点来优化查找过程。具体来说，我们只需要关注每个数组的最大值和最小值，因为这些值决定了该数组与其他数组之间可能产生的最大距离。

解决方案

  1. 初始化：我们需要跟踪当前遇到的最小值min_val、最大值max_val以及最大距离max_distance。开始时，可以从第一个数组中选取最小值和最大值作为初始值。

  2. 遍历数组：对于每一个数组，计算当前数组的最大值与之前记录的最小值之间的差值，以及当前数组的最小值与之前记录的最大值之间的差值。这两个差值中的较大者可能是新的最大距离。

  3. 更新：在每一步之后，更新min_val和max_val以反映最新的最小值和最大值。

  4. 避免同一数组：由于我们总是从不同的数组中选择数值，所以无需担心会从同一个数组中选取最大值和最小值。

下面是具体的Python实现：

python
class Solution:
    def maxDistance(self, arrays: List[List[int]]) -> int:
        # 初始化第一个数组的最小值和最大值
        min_val, max_val = arrays[0][0], arrays[0][-1]
        max_distance = 0
        
        for array in arrays[1:]:
            # 计算当前数组能提供的最大距离
            current_max_distance = max(abs(array[-1] - min_val), abs(max_val - array[0]))
            # 更新最大距离
            max_distance = max(max_distance, current_max_distance)
            # 更新全局最小值和最大值
            min_val = min(min_val, array[0])
            max_val = max(max_val, array[-1])
        
        return max_distance

这种方法的时间复杂度是O(m)，其中m是数组的数量，因为我们只需遍历一次所有数组。空间复杂度是O(1)，因为我们只使用了有限的额外空间。这使得它非常适合处理大规模数据集。