0624. 数组列表中的最大距离【中等】
1. 📝 题目描述
给定 m 个数组，每个数组都已经按照升序排好序了。
现在你需要从两个不同的数组中选择两个整数（每个数组选一个）并且计算它们的距离。两个整数 a 和 b 之间的距离定义为它们差的绝对值 |a-b|。
返回最大距离。
示例 1：
txt
输入：[[1,2,3],[4,5],[1,2,3]]
输出：4
解释：
一种得到答案 4 的方法是从第一个数组或者第三个数组中选择 1，同时从第二个数组中选择 5。1
2
3
4
2
3
4
示例 2：
txt
输入：arrays = [[1],[1]]
输出：01
2
2
提示：
m == arrays.length2 <= m <= 10^51 <= arrays[i].length <= 500-10^4 <= arrays[i][j] <= 10^4arrays[i]以 升序 排序。- 所有数组中最多有
10^5个整数。
2. 🎯 s.1 - 一次遍历
c
int maxDistance(int** arrays, int arraysSize, int* arraysColSize) {
int minVal = arrays[0][0];
int maxVal = arrays[0][arraysColSize[0] - 1];
int res = 0;
for (int i = 1; i < arraysSize; i++) {
int curMin = arrays[i][0];
int curMax = arrays[i][arraysColSize[i] - 1];
int d1 = curMax - minVal; if (d1 < 0) d1 = -d1;
int d2 = maxVal - curMin; if (d2 < 0) d2 = -d2;
if (d1 > res) res = d1;
if (d2 > res) res = d2;
if (curMin < minVal) minVal = curMin;
if (curMax > maxVal) maxVal = curMax;
}
return res;
}1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
js
/**
* @param {number[][]} arrays
* @return {number}
*/
var maxDistance = function (arrays) {
let minVal = arrays[0][0]
let maxVal = arrays[0][arrays[0].length - 1]
let res = 0
for (let i = 1; i < arrays.length; i++) {
const curMin = arrays[i][0]
const curMax = arrays[i][arrays[i].length - 1]
res = Math.max(res, Math.abs(curMax - minVal), Math.abs(maxVal - curMin))
minVal = Math.min(minVal, curMin)
maxVal = Math.max(maxVal, curMax)
}
return res
}1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
py
class Solution:
def maxDistance(self, arrays: List[List[int]]) -> int:
min_val, max_val = arrays[0][0], arrays[0][-1]
res = 0
for i in range(1, len(arrays)):
cur_min, cur_max = arrays[i][0], arrays[i][-1]
res = max(res, abs(cur_max - min_val), abs(max_val - cur_min))
min_val = min(min_val, cur_min)
max_val = max(max_val, cur_max)
return res1
2
3
4
5
6
7
8
9
10
2
3
4
5
6
7
8
9
10
- 时间复杂度：
- 空间复杂度：
算法思路：
- 维护已遍历数组的全局最小值和最大值
- 每遍历一个新数组，用其首尾元素与已有最值求距离，确保不同数组