Medium
题目描述
给你 m 个数组，每个数组都已按 升序 排列。
你可以从两个不同的数组中各选一个整数（每个数组选择一个），然后计算它们的距离。我们定义两个整数 a 和 b 之间的距离为它们差的绝对值 |a - b|。
返回最大距离。
示例 1：
输入：arrays = [[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
- -10^4 <= arrays[i][j] <= 10^4
- arrays[i] 按升序排列
- 所有数组中最多有 10^5 个整数
解题思路
解题思路
这道题要求从两个不同数组中各选一个数，使得它们的距离最大。由于每个数组都是升序排列的，我们只需要考虑每个数组的最大值和最小值。
核心思想： 最大距离一定出现在某个数组的最小值与另一个数组的最大值之间。
贪心策略：
- 维护当前遍历过的所有数组的全局最小值和全局最大值
- 对于当前数组，计算其最小值与之前数组最大值的距离，以及其最大值与之前数组最小值的距离
- 更新全局最小值、最大值和最大距离
算法流程：
- 初始化全局最小值和最大值为第一个数组的最小值和最大值
- 从第二个数组开始遍历，对于每个数组：
- 计算当前数组最小值与全局最大值的距离
- 计算当前数组最大值与全局最小值的距离
- 更新最大距离
- 更新全局最小值和最大值
这种方法避免了嵌套循环，时间复杂度为 O(m)，其中 m 是数组个数。
代码实现
class Solution {
public:
int maxDistance(vector<vector<int>>& arrays) {
int minVal = arrays[0][0];
int maxVal = arrays[0].back();
int maxDist = 0;
for (int i = 1; i < arrays.size(); i++) {
int currMin = arrays[i][0];
int currMax = arrays[i].back();
maxDist = max(maxDist, max(abs(currMax - minVal), abs(maxVal - currMin)));
minVal = min(minVal, currMin);
maxVal = max(maxVal, currMax);
}
return maxDist;
}
};
class Solution:
def maxDistance(self, arrays: List[List[int]]) -> int:
min_val = arrays[0][0]
max_val = arrays[0][-1]
max_dist = 0
for i in range(1, len(arrays)):
curr_min = arrays[i][0]
curr_max = arrays[i][-1]
max_dist = max(max_dist, max(abs(curr_max - min_val), abs(max_val - curr_min)))
min_val = min(min_val, curr_min)
max_val = max(max_val, curr_max)
return max_dist
public class Solution {
public int MaxDistance(IList<IList<int>> arrays) {
int minVal = arrays[0][0];
int maxVal = arrays[0][arrays[0].Count - 1];
int maxDist = 0;
for (int i = 1; i < arrays.Count; i++) {
int currMin = arrays[i][0];
int currMax = arrays[i][arrays[i].Count - 1];
maxDist = Math.Max(maxDist, Math.Max(Math.Abs(currMax - minVal), Math.Abs(maxVal - currMin)));
minVal = Math.Min(minVal, currMin);
maxVal = Math.Max(maxVal, currMax);
}
return maxDist;
}
}
var maxDistance = function(arrays) {
let minVal = arrays[0][0];
let maxVal = arrays[0][arrays[0].length - 1];
let maxDist = 0;
for (let i = 1; i < arrays.length; i++) {
const currMin = arrays[i][0];
const currMax = arrays[i][arrays[i].length - 1];
maxDist = Math.max(maxDist, Math.max(Math.abs(currMax - minVal), Math.abs(maxVal - currMin)));
minVal = Math.min(minVal, currMin);
maxVal = Math.max(maxVal, currMax);
}
return maxDist;
};
复杂度分析
| 复杂度类型 | 值 |
|---|---|
| 时间复杂度 | O(m) |
| 空间复杂度 | O(1) |
其中 m 是数组的个数。我们只需要遍历一次所有数组，每次操作都是常数时间，因此时间复杂度为 O(m)。只使用了常数个额外变量，空间复杂度为 O(1)。