数组列表中的最大距离-LeetCode

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

🎯 问题描述（来源于LeetCode）

描述：
给定 m 个已按升序排列的数组，你需要从两个不同的数组中各选一个整数，计算它们的距离（即两数差的绝对值），并返回所有可能选择中的最大距离。

说明：

• 这是一个贪心算法问题。

• 核心逻辑是：最大距离一定由某个数组的最小值和另一个数组的最大值构成。

• 由于数组已经排序，每个数组的最小值是其第一个元素，最大值是其最后一个元素。

• 通过一次遍历，维护已遍历数组的最小值和最大值，并在每一步计算当前数组与之前数组的最大距离。

• 示例：

• 示例 1：

输入：arrays = [[1,2,3],[4,5],[1,2,3]]
输出：4
解释：
- 从第一个数组选 1，从第二个数组选 5，距离 = |5-1| = 4。
- 这是最大距离。

• 示例 2：

输入：arrays = [[1],[1]]
输出：0
解释：
- 只能选 1 和 1，距离 = 0。

💻 解题思路

思路1：贪心算法（一次遍历）

思路1：代码实现

class Solution:
    def maxDistance(self, arrays: List[List[int]]) -> int:
        m = len(arrays)
        # 初始化第一个数组的最小值和最大值
        min_num = arrays[0][0]
        max_num = arrays[0][-1]
        d = 0
        
        # 从第二个数组开始遍历
        for n in range(1, m):
            # 计算当前数组与之前数组的最大距离
            # 情况1：当前数组的最大值 - 之前数组的最小值
            # 情况2：之前数组的最大值 - 当前数组的最小值
            d = max(arrays[n][-1] - min_num, max_num - arrays[n][0], d)
            
            # 更新已遍历数组的最小值和最大值
            min_num = min(min_num, arrays[n][0])
            max_num = max(max_num, arrays[n][-1])
            
        return d

思路1：📊 性能分析

• 时间复杂度：$O(M)$
  • 其中 $M$ 是数组 arrays 的长度。
  • 我们只遍历数组一次，每次操作都是常数时间。
  • 总时间复杂度为 $O(M)$。
• 空间复杂度：$O(1)$
  • 只使用了常数个额外变量（min_num, max_num, d）。

思考

1. 贪心策略：

   • 最大距离一定由某个数组的最小值和另一个数组的最大值构成。
   • 因为数组已排序，每个数组的最小值是 arrays[i][0]，最大值是 arrays[i][-1]。
   • 我们需要从两个不同的数组中选择，所以不能从同一个数组中取最小值和最大值。

2. 遍历逻辑：

   • 我们从第二个数组开始遍历（n = 1），因为第一个数组已经用于初始化 min_num 和 max_num。
   • 对于每个数组 arrays[n]，我们计算它与之前所有数组的最大距离：
     • arrays[n][-1] - min_num：当前数组的最大值与之前数组的最小值的差。
     • max_num - arrays[n][0]：之前数组的最大值与当前数组的最小值的差。
   • 取这两个差值的最大值，并更新全局最大距离 d。

3. 更新逻辑：

   • 在计算完当前数组的距离后，我们将当前数组的最小值和最大值纳入 min_num 和 max_num。
   • 这样可以确保后续数组可以与当前数组进行距离计算。

4. 边界情况：

   • 只有两个数组：直接计算两个数组之间的最大距离。
   • 所有数组相同：最大距离为 0。
   • 数组长度为 1：每个数组只有一个元素，逻辑依然正确。