[LeetCode] 每日一题 624. 数组列表中的最大距离

题目链接

https://leetcode.cn/problems/maximum-distance-in-arrays

题目描述

给定 m 个数组，每个数组都已经按照升序排好序了。

现在你需要从两个不同的数组中选择两个整数（每个数组选一个）并且计算它们的距离。两个整数 a 和 b 之间的距离定义为它们差的绝对值 |a-b| 。

示例输入

示例 1

输入：[[1,2,3],[4,5],[1,2,3]]
输出：4
解释：
一种得到答案 4 的方法是从第一个数组或者第三个数组中选择 1，同时从第二个数组中选择 5 。

示例 2

输入：arrays = [[1],[1]]
输出：0

提示

• m == arrays.length

• 2 <= m <= 10^5

• 1 <= arrays[i].length <= 500

• -104 <= arrays[i][j] <= 10^4

• arrays[i] 以 升序 排序。

• 所有数组中最多有 10^5 个整数。

解题思路

这道题目要求我们在多个已排好序的数组中，选择两个不同数组中的元素，计算它们的距离，并返回最大距离。暴力解法是通过双重循环，遍历所有数组元素对，计算它们的差值，但这种方法 时间复杂度较高，在数组数量较大时无法通过。

然而，由于每个数组已经排好序，我们可以利用这一点进行优化。每个数组的 最小值总是在开头，最大值总是在末尾，这就意味着，我们可以通过一次遍历来维护当前的 最小值 和 最大值。对于每个新数组，我们计算其最小值与当前最大值、最大值与当前最小值之间的差值，并更新最大差值。

但有一个关键点需要特别注意： 单个数组的最大值和最小值之间的差值不能直接用于计算结果，因为我们要求的是来自 两个不同数组 的元素。因此，最大距离的计算需要基于 当前数组与前一个数组的最小值和最大值的比较，而不是单纯考虑当前数组的最小值和最大值。这就要求我们 预先求出最大值和最小值，然后在下一个数组中进行比较，这样就能有效“错开”不同数组之间的比较，避免错误。

代码实现

class Solution {
    public int maxDistance(List<List<Integer>> arrays) {
        int ans = 0;
        int min = arrays.get(0).get(0); // 初始数组的最小值
        int max = arrays.get(0).get(arrays.get(0).size() - 1); // 初始数组的最大值
        for (int i = 1; i < arrays.size(); i++) {
            int tempMin = arrays.get(i).get(0); // 当前数组的最小值
            int tempMax = arrays.get(i).get(arrays.get(i).size() - 1); // 当前数组的最大值
            // 更新最大差值
            ans = Math.max(ans, Math.max(Math.abs(tempMax - min), Math.abs(tempMin - max)));
            // 更新全局最小值和最大值
            max = Math.max(max, tempMax);
            min = Math.min(min, tempMin);
        }
        return ans;
    }
}

复杂度分析

• 时间复杂度：O(m)，其中 m 是数组的个数。我们只需要遍历一次所有数组，每次获取每个数组的最小值和最大值，更新最大距离。因此，时间复杂度是 O(m)

• 空间复杂度：O(1)，我们只需要几个常数空间来存储当前的最小值、最大值和答案，因此空间复杂度是 O(1)。

总结

这道题目考察了如何利用 已排序数组的特性 进行优化。尽管可以通过 暴力解法 计算所有可能的元素对，但这种方法时间复杂度较高，难以通过。通过一次遍历 维护最小值和最大值，我们能高效地计算出最大距离，避免了重复计算，降低了时间复杂度。

特别需要注意的是，单数组的最大值和最小值的差值不能直接用于计算最终结果，必须预先计算并在后续数组中进行比较，才能确保最大距离的正确计算。

希望这篇分享能为你带来启发！如果你有任何问题或建议，欢迎在评论区留言，与我共同交流探讨。