LeetCode0624.数组列表中的最大距离：只关心最小最大值

【LetMeFly】624.数组列表中的最大距离：只关心最小最大值

力扣题目链接： leetcode /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.length2 <= m <= 1051 <= arrays[i].length <= 500-104 <= arrays[i][j] <= 104arrays[i] 以 升序 排序。所有数组中最多有 105 个整数。

 

解题方法：只关心最小最大值

对于两个数组，抽象的画一画，大约一共有以下三种可能：（若有两端点相等也不影响结果）

不重合

---- -----

重合不包含

------- -------

包含

-------- ----

分别从两个数组中取一个元素，想让差值的绝对值最大，怎么取？很容易发现一定要从数组边界取值（要么取数组的最大值，要么取最小值，否则最大/小值与另一个数组的差值可以更大）。

也就是说：

我们只需要维护数组最大值和最小值，并且保证两个值不会取自同一个数组不就行了么。

时间复杂度 O ( l e n ( a r r a y s ) ) O(len(arrays)) O(len(arrays))空间复杂度 O ( 1 ) O(1) O(1) AC代码 C++ /* * @Author: LetMeFly * @Date: 2025-02-19 17:37:04 * @LastEditors: LetMeFly.xyz * @LastEditTime: 2025-02-19 17:46:16 */ /* ---- ----- ------- ------- -------- ---- */ class Solution { public: int maxDistance(vector<vector<int>>& arrays) { int ans = 0; int mLeft = 100000, MRight = -100000; for (vector<int>& a : arrays) { ans = max(ans, max(a.back() - mLeft, MRight - a[0])); mLeft = min(mLeft, a[0]), MRight = max(MRight, a.back()); } return ans; } }; Python ''' Author: LetMeFly Date: 2025-02-19 17:47:16 LastEditors: LetMeFly.xyz LastEditTime: 2025-02-19 17:49:04 ''' from typing import List class Solution: def maxDistance(self, arrays: List[List[int]]) -> int: ans = 0 m, M = 100000, -100000 for a in arrays: ans = max(ans, M - a[0], a[-1] - m) m, M = min(m, a[0]), max(M, a[-1]) return ans Java /* * @Author: LetMeFly * @Date: 2025-02-19 17:47:53 * @LastEditors: LetMeFly.xyz * @LastEditTime: 2025-02-19 17:51:18 */ import java.util.List; class Solution { public int maxDistance(List<List<Integer>> arrays) { int ans = 0; int m = 100000, M = -100000; for (List<Integer> a : arrays) { ans = Math.max(ans, Math.max(a.get(a.size() - 1) - m, M - a.get(0))); m = Math.min(m, a.get(0)); M = Math.max(M, a.get(a.size() - 1)); } return ans; } } Go /* * @Author: LetMeFly * @Date: 2025-02-19 17:47:56 * @LastEditors: LetMeFly.xyz * @LastEditTime: 2025-02-19 17:53:37 */ package main func maxDistance(arrays [][]int) (ans int) { m, M := 100000, -100000 for _, a := range arrays { ans = max(ans, max(a[len(a) - 1] - m, M - a[0])) m, M = min(m, a[0]), max(M, a[len(a) - 1]) } return }

同步发文于CSDN和我的个人博客，原创不易，转载经作者同意后请附上原文链接哦~

千篇源码题解已开源

Tisfy： blog.letmefly.xyz/2025/02/19/LeetCode 0624.数组列表中的最大距离/