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

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

function maxDistance(arrays: number[][]): number {
  let result = 0
  let minSoFar = arrays[0][0] // 第一个数组的最小值
  let maxSoFar = arrays[0][arrays[0].length - 1] // 第一个数组的最大值

  for (let i = 1; i < arrays.length; i++) {
    const current = arrays[i]
    const curMin = current[0]
    const curMax = current[current.length - 1]

    // 当前数组与历史最大/最小值组合出两个候选答案
    const dist1 = Math.abs(curMax - minSoFar) // 当前最大 - 历史最小
    const dist2 = Math.abs(maxSoFar - curMin) // 历史最大 - 当前最小

    result = Math.max(result, dist1, dist2)

    // 更新历史最大/最小
    minSoFar = Math.min(minSoFar, curMin)
    maxSoFar = Math.max(maxSoFar, curMax)
  }

  return result
}

隐藏条件

题干里有一个关键约束：每个数组都是已排序的。这意味着每个数组的最小值在 [0]，最大值在 [length-1]。

同时，最大距离的两个元素必须来自不同数组。如果忽略这个约束，直接全局找最大最小值即可。有了它，问题变成：在遍历过程中，用「历史最佳」和「当前」组合出答案。

为什么先组合再更新

顺序很重要。对于每个新数组，我们先用它的极值与之前所有数组的极值计算距离，然后再用它的极值更新历史记录。这样保证不会出现「同一个数组的两个元素」参与距离计算的情况。

遍历 O(N)，空间 O(1)。这一类题的关键就是在遍历过程中维护历史极值，再和当前项组合。