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

2025-12-29 HGNULB 约 7 分钟

文章信息 6 个分类 2 个标签

分类

题目描述

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

题意分析

要什么：给若干个各自内部已升序的整数数组，从两个不同的数组里各挑一个数，让两数之差的绝对值最大，返回这个最大值。
约束透露的信号：每个数组内部有序，这意味着一个数组里只有第一个元素和最后一个元素可能成为最优配对的一端，中间元素永远被首尾夹住，可以整体丢弃，于是每个数组被压缩成一个二元组 (首, 尾)。数组个数可以很大而每次只需要看两个端点，说明期望的是一遍线性扫描，而不是两两枚举数组对。
边界：两个数必须来自不同数组，所以同一个数组自己的首尾之差不能计入答案；元素可以是负数，答案的初值不能拍脑袋写成某个具体数字，只能从合法配对里产生；所有数组元素完全相同时答案是 0，这是合法结果而不是无解。

解法：一次扫描维护全局最小/最大

核心思路

最直白的做法是枚举所有数组对 (i, j)，答案在 arrays[j] 的尾减 arrays[i] 的首、arrays[i] 的尾减 arrays[j] 的首这两个候选里取最大。这是对的，但要做 $O(m^2)$ 次配对，$m$ 是数组个数。
瓶颈在于：固定右边那个数组 j 时，程序把左边所有数组又重新翻了一遍，而它真正想知道的只有两件事——左边所有数组里最小的首元素是多少、最大的尾元素是多少。这两个量完全可以边扫边攒，不必每次重算。
由此得到要维护的不变量：处理到下标 i 时，globalMin 是 arrays[0..i-1] 所有首元素的最小值，globalMax 是 arrays[0..i-1] 所有尾元素的最大值。这两个量描述的是「严格在 i 左边的那些数组」，所以只要先用它们算答案、再把 arrays[i] 并进去，两端天然来自不同数组，「不同数组」这个约束就被顺序本身保证了，不需要任何额外判重。
还需要说明为什么只看「左边 × 当前」就够：任意一对数组必有先后，把它当成 (左边某个, 当前这个) 来看，一定会在扫到后者的那一轮被枚举到，所以没有配对被遗漏。

解题步骤

先把 arrays[0] 的首尾装进 globalMin 和 globalMax，答案初始化为 0。为什么从第 0 个开始装：不变量要求扫描第 i 个数组时左边非空，所以第 0 个数组只能充当「左边」，不参与本轮取答案。答案初始为 0 是安全的，因为差值的绝对值本身非负，且题目保证至少有两个数组。

从 i = 1 开始遍历，取出当前数组的首 curMin 与尾 curMax。为什么只取首尾：数组升序，任何中间元素当左端都不比首元素小、当右端都不比尾元素大，留着只会拖慢速度。

用 curMax - globalMin 和 globalMax - curMin 两个候选更新答案。为什么是这两个：最大距离要么是「当前数组出最大值、左边出最小值」，要么反过来，两种方向都要试；写成这两个减法后结果天然非负或被 0 兜住，不需要额外取绝对值。

把 curMin、curMax 并入 globalMin、globalMax。为什么必须放在取答案之后：一旦先更新，globalMin 可能就是当前数组自己的首元素，curMax - globalMin 就退化成同一个数组的首尾之差，直接违反「来自不同数组」。

以 arrays = [[1,2,3],[4,5],[1,2,3]] 走一遍：初始化 globalMin = 1、globalMax = 3、ans = 0。i = 1 时 curMin = 4、curMax = 5，候选 5 - 1 = 4 把答案抬到 4，候选 3 - 4 = -1 不起作用，随后 globalMin 仍是 1、globalMax 更新为 5。i = 2 时 curMin = 1、curMax = 3，候选 3 - 1 = 2 与 5 - 1 = 4 都不超过当前答案，全局最值保持 1 和 5。循环结束返回 4，对应第 0 个数组取 1、第 1 个数组取 5。注意最后一轮的 5 - 1 = 4 里的 5 来自第 1 个数组、1 来自第 2 个数组，正是「先取答案后更新」让这次跨数组配对合法。

代码实现

// 核心实现：一次扫描维护全局最小/最大，维护必要状态并避免重复处理。
class Solution {
    public int maxDistance(List<List<Integer>> arrays) {
        int globalMin = arrays.get(0).get(0);
        List<Integer> first = arrays.get(0);
        int globalMax = first.get(first.size() - 1);

        int answer = 0;
        for (int i = 1; i < arrays.size(); i++) {
            List<Integer> arr = arrays.get(i);
            int curMin = arr.get(0);
            int curMax = arr.get(arr.size() - 1);

            answer = Math.max(answer, curMax - globalMin);
            answer = Math.max(answer, globalMax - curMin);

            globalMin = Math.min(globalMin, curMin);
            globalMax = Math.max(globalMax, curMax);
        }

        return answer;
    }
}

// 核心实现：一次扫描维护全局最小/最大，维护必要状态并避免重复处理。
func maxDistance(arrays [][]int) int {
    globalMin := arrays[0][0]
    globalMax := arrays[0][len(arrays[0])-1]
    answer := 0

    for i := 1; i < len(arrays); i++ {
        arr := arrays[i]
        curMin := arr[0]
        curMax := arr[len(arr)-1]

        if curMax-globalMin > answer {
            answer = curMax - globalMin
        }
        if globalMax-curMin > answer {
            answer = globalMax - curMin
        }

        if curMin < globalMin {
            globalMin = curMin
        }
        if curMax > globalMax {
            globalMax = curMax
        }
    }

    return answer
}

复杂度分析

时间复杂度：$O(m)$，$m$ 为数组个数。凭什么：每个数组只被访问一次，且只读取首尾两个位置，与数组内部长度无关，没有排序也没有嵌套循环。

空间复杂度：$O(1)$。凭什么：全程只有 globalMin、globalMax、ans 三个标量，没有开辅助数组，也没有递归栈。

关键点总结

有序性是压缩信息的杠杆：内部升序意味着一个数组对答案的全部贡献只有首尾两个数，识别出「哪些数据其实用不上」往往比优化循环更能降复杂度。

「枚举配对」几乎都能改写成「固定右端 + 维护左侧前缀极值」，这条路子在买卖股票、最佳观光组合、最大子数组和这类题里反复出现，是一个可以直接迁移的模板。

更新时机就是约束本身：本题不用任何标记来保证两数来自不同数组，只靠「先算后更新」的顺序。面试里能主动点出这一点，比写对代码更能体现你理解了不变量。

面试视角：先给出 $O(m^2)$ 的暴力并说清正确性，再指出重复计算的位置并优化到 $O(m)$，这个「暴力 → 定位冗余 → 优化」的叙述顺序是面试官真正在打分的部分。

涉及负数的极值题，初值要么取自第一个合法元素，要么用语言的极小值常量，凭直觉写 0 是高频翻车点。

易错点总结

错误写法：先更新 globalMin/globalMax 再计算答案；用例 [[1,10],[2,3]] → 处理第 1 个数组时 globalMax 已被抬到 10，算出 10 - 2 = 8，但 10 和 2 分别来自不同数组还算走运；换成 [[1,10],[11,12]] 处理第 0 个数组自身就会得到 10 - 1 = 9，返回同一数组的首尾之差，答案偏大。

错误写法：把答案初始化为某个具体正数或忘记初始化为 0；用例 [[1,1],[1,1]] → 正确答案是 0，若初值写成 1 会直接返回 1。

错误写法：遍历时用 arr.get(1) 取尾元素；用例 [[1,2,3],[4,5]] → 第 0 个数组的尾应该是 3 却取成 2，最终答案从 4 变成 4 以外的错误值，长度大于 2 的数组全部算错。

错误写法：只算 curMax - globalMin 一个方向；用例 [[9,10],[1,2]] → 只得到 2 - 9 = -7，答案退化成 0，漏掉了 10 - 1 = 9。

错误写法：对候选值套绝对值再比较，例如 Math.abs(curMax - globalMin)；用例 [[5,6],[1,2]] → 处理第 1 个数组时 |2 - 5| = 3 被当成合法距离，但这个 3 并不对应任何一对「左端小、右端大」的合法取法，虽然本例恰好不超过真实答案 5，构造更极端的数据就会返回偏大的结果。

错误写法：循环从 i = 0 开始且照常取答案；用例 [[1,100],[2,3]] → 第 0 轮用自己的首尾算出 99，直接返回 99，而正确答案是 98。

错误写法：把每个数组重新排序或遍历全部元素求最值；用例数组总长度很大时 → 结果虽对但时间退化到 $O(\sum len)$ 甚至 $O(\sum len \log len)$，浪费了题目给的有序条件，面试会被追问。

错误写法：用 int 存中间差值却假设元素非负从而省略比较；用例 [[-100,-50],[50,100]] → 若把 globalMin 初始化为 0，第 1 轮算出 100 - 0 = 100，超过真实答案 200 的对手值不说，globalMin 语义已经错了，后续全盘失真。

错误写法：Java 里用 arrays.get(i).size() - 1 之外的下标或 Go 里写成 arr[len(arr)]；用例任意输入 → 直接数组越界异常。

相似题目

题目	难度	考察点
121. 买卖股票的最佳时机	简单	同样是「固定右端 + 前缀最小值」，但两端必须满足先后顺序而非分属不同集合
53. 最大子数组和	中等	从维护前缀极值升级为维护前缀和的最小值，答案由减法变成区间和
561. 数组拆分	简单	同样靠有序性做贪心配对，但需要证明排序后相邻两两配对最优