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

约 4 分钟
文章信息 6 个分类 2 个标签
分类
LeetCode CodeTop 中等 未解决 1-2 B站
标签
数组 贪心

题目描述

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

image-20260929102018173

image-20260929102018276

题意分析

从两个不同的升序数组中各取一个整数，使两数差的绝对值最大。限制在于来源数组必须不同，所以不能直接取全部元素的最大值减最小值，它们可能来自同一个数组。

每个数组已经有序，只需关注首项与末项；中间值不会比端点产生更大的跨数组距离。

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

核心思路

[!blue]
从左到右处理数组，用 globalMin 保存此前所有数组的最小首项，globalMax 保存最大末项。处理当前数组时，读取它的 curMin 和 curMax，只需考虑两种方向。

如果当前数组提供较大数，最优配对是 curMax - globalMin；如果此前数组提供较大数，最优配对是 globalMax - curMin。这两个方向已经覆盖绝对值的两种情况，不需要再遍历内部元素或单独取绝对值。

必须先用这两个候选更新答案，再把当前首尾并入全局极值。计算候选时，全局极值只来自此前数组，因此与当前元素配对一定满足来源不同；如果先更新，就可能错误地选择当前数组自己的首尾。

任意两个不同数组总有一个先出现、一个后出现。扫描到后者时，前者已经包含在历史极值中，它们能产生的最佳距离一定被本轮候选覆盖。保留此前答案并逐轮更新，就得到全部数组对的最大距离。

解题步骤

  1. 用第一个数组的首尾初始化此前极值。
  2. 从第二个数组开始，读取当前首尾。
  3. 计算两个跨数组方向的候选。
  4. 随后更新全局极值，继续扫描。

答案初始为零，因为距离不会为负。单元素数组的首尾相同，仍按同一流程处理；多个数组中的值全相同时，结果保持为零。

代码实现

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)$。

关键点总结

[!green]

  • 先配对再更新，顺序保证来源不同。
  • 两个方向都要比较，当前数组可能提供最小值，也可能提供最大值。
  • 绝对距离非负，答案初始化零是合法下界。

易错点总结

[!yellow]

  • 先更新极值：可能选中当前数组自己的首尾。
  • 只算一个方向：漏掉此前最大值与当前最小值的组合。
  • 从第一个数组就开始配对：会把同数组内部距离算进答案。
  • 遍历全部内部元素找极值：没有利用已有排序。

相似题目

题目 难度 关联与区别
121. 买卖股票的最佳时机 简单 同样扫描时保留此前极值，但本题必须先用当前数组与旧极值比较，再更新，避免两值来自同一数组。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2025/39881429
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！