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
}

题目要点

「624. 数组列表中的最大距离」的关键不是把流程写出来，而是先定义序列不变量，并确保每一次遍历/交换都不会破坏该不变量。

思路拆解

1. 明确状态含义：当前索引、窗口边界、候选答案分别表示什么。
2. 先给出直观解法，再说明为什么需要优化到目标复杂度。
3. 逐步引入数据结构（Set/Map/双指针/二分）来消除重复扫描。

复杂度分析

• 时间复杂度：以代码实现为准，核心取决于是否存在重复遍历或嵌套回扫。
• 空间复杂度：重点关注辅助集合与中间数组的规模是否与输入同阶。

边界与测试

1. 空数组、单元素、全部重复值。
2. 单调序列、逆序序列、已满足条件的输入。
3. 极值与退化场景（如大量重复导致分支频繁命中）。

工程实践

将“状态转移条件”写成可读的布尔表达式，并在关键分支补充注释，方便后续重构与复盘。

总结

这类数组题的复用价值在于沉淀不变量模板：先定约束，再定遍历策略，最后用复杂度与边界用例验证正确性。