class Solution {
public:
int maxDistance(vector<vector<int>>& arrays) {
}
};
624. 数组列表中的最大距离
给定 m 个数组，每个数组都已经按照升序排好序了。现在你需要从两个不同的数组中选择两个整数（每个数组选一个）并且计算它们的距离。两个整数 a 和 b 之间的距离定义为它们差的绝对值 |a-b| 。你的任务就是去找到最大距离
示例 1：
输入： [[1,2,3], [4,5], [1,2,3]] 输出： 4 解释： 一种得到答案 4 的方法是从第一个数组或者第三个数组中选择 1，同时从第二个数组中选择 5 。
注意：
m 个数组中的数字总数目在范围 [2, 10000] 内。m 个数组中所有整数的范围在 [-10000, 10000] 内。
原站题解
cpp 解法, 执行用时: 0 ms, 内存消耗: 105.7 MB, 提交时间: 2025-02-19 09:17:20
class Solution {
public:
int maxDistance(vector<vector<int>>& arrays) {
int ans = 0;
int mn = INT_MAX / 2, mx = INT_MIN / 2; // 防止减法溢出
for (auto& a : arrays) {
ans = max({ans, a.back() - mn, mx - a[0]});
mn = min(mn, a[0]);
mx = max(mx, a.back());
}
return ans;
}
};
java 解法, 执行用时: 6 ms, 内存消耗: 62.3 MB, 提交时间: 2025-02-19 09:17:07
class Solution {
public int maxDistance(List<List<Integer>> arrays) {
int ans = 0;
int mn = Integer.MAX_VALUE / 2; // 防止减法溢出
int mx = Integer.MIN_VALUE / 2;
for (List<Integer> a : arrays) {
int x = a.get(0);
int y = a.get(a.size() - 1);
ans = Math.max(ans, Math.max(y - mn, mx - x));
mn = Math.min(mn, x);
mx = Math.max(mx, y);
}
return ans;
}
}
javascript 解法, 执行用时: 4 ms, 内存消耗: 73.3 MB, 提交时间: 2025-02-19 09:16:53
/**
* @param {number[][]} arrays
* @return {number}
*/
var maxDistance = function(arrays) {
let ans = 0;
let mn = Infinity, mx = -Infinity;
for (const a of arrays) {
ans = Math.max(ans, a[a.length - 1] - mn, mx - a[0]);
mn = Math.min(mn, a[0]);
mx = Math.max(mx, a[a.length - 1]);
}
return ans;
};
rust 解法, 执行用时: 7 ms, 内存消耗: 8 MB, 提交时间: 2025-02-19 09:16:41
impl Solution {
pub fn max_distance(arrays: Vec<Vec<i32>>) -> i32 {
let mut ans = 0;
let mut mn = i32::MAX / 2; // 防止减法溢出
let mut mx = i32::MIN / 2;
for a in arrays {
let x = a[0];
let y = a[a.len() - 1];
ans = ans.max(y - mn).max(mx - x);
mn = mn.min(x);
mx = mx.max(y);
}
ans
}
}
golang 解法, 执行用时: 0 ms, 内存消耗: 17.9 MB, 提交时间: 2025-02-19 09:16:27
func maxDistance(arrays [][]int) (ans int) {
mn, mx := math.MaxInt/2, math.MinInt/2 // 防止减法溢出
for _, a := range arrays {
x, y := a[0], a[len(a)-1]
ans = max(ans, y-mn, mx-x)
mn = min(mn, x)
mx = max(mx, y)
}
return
}
python3 解法, 执行用时: 90 ms, 内存消耗: 33.1 MB, 提交时间: 2025-02-19 09:16:07
class Solution:
# 枚举右，维护左
def maxDistance(self, arrays: List[List[int]]) -> int:
ans = 0
mn, mx = inf, -inf
for a in arrays:
ans = max(ans, a[-1] - mn, mx - a[0])
mn = min(mn, a[0])
mx = max(mx, a[-1])
return ans