难度: Medium
Submission
运行时间: 84 ms
内存: 31.7 MB
class Solution:
def maxDistance(self, arrays: List[List[int]]) -> int:
min = 10000
max = -1000
for i in arrays:
if i[0]< min:
min = i[0]
y =i
for i in arrays:
if i[-1]> max:
max = i[-1]
x = i
dis = 0
for i in arrays:
if ((i[-1]-min)>dis) and (i is not y):
dis = i[-1]-min
if ((max- i[0])>dis) and (i is not x):
dis = max - i[0]
return dis
Explain
该题解的思路是先遍历数组列表找到最小值和最大值及其对应的数组，然后再次遍历数组列表，计算每个数组的最后一个元素与最小值的差值，以及每个数组的第一个元素与最大值的差值，取其中的最大值作为结果，同时要排除最小值和最大值所在的数组。
时间复杂度: O(m)
空间复杂度: O(1)
class Solution:
def maxDistance(self, arrays: List[List[int]]) -> int:
min_val = 10000
max_val = -1000
for i in arrays:
if i[0] < min_val:
min_val = i[0]
min_arr = i
for i in arrays:
if i[-1] > max_val:
max_val = i[-1]
max_arr = i
dis = 0
for i in arrays:
if ((i[-1] - min_val) > dis) and (i is not min_arr):
dis = i[-1] - min_val
if ((max_val - i[0]) > dis) and (i is not max_arr):
dis = max_val - i[0]
return dis
Explore
在题解中选择10000和-1000作为初始的最小值和最大值是为了确保在遍历过程中，任何数组的元素都能更新这些初始值。这种做法假设了输入数组中的元素值不会超出这些范围。然而，如果输入的数据包含比-1000更小或比10000更大的值，这个方法就会失败。更好的做法是将初始的最小值设置为正无穷大（如float('inf')），最大值设置为负无穷大（如float('-inf')），这样可以处理任意范围的输入值。
排除最小值和最大值所在的数组是为了避免在计算最大距离时误用数组内部的最小值和最大值，从而导致计算的结果不是两个不同数组间的值的差。如果不排除这两个数组，我们可能会得到一个数组内部两个元素的差值，而不是题目要求的两个不同数组间的最大距离。这种做法确保了距离的计算是跨数组的，符合题目的要求。
是的，可以通过减少遍历次数来优化算法。可以在单个遍历中同时找到最小值、最小值所在数组、最大值和最大值所在数组。然后，再进行一次遍历来计算最大距离。这样，总的遍历次数可以从三次减少到两次。
在本题的上下文中，只考虑数组的第一个和最后一个元素是有效的，因为数组中所有元素都假定为已排序。因此，数组的最小值总是第一个元素，最大值总是最后一个元素。如果数组未排序，那么仅考虑首尾元素将不足以找到真正的最小值和最大值，此时需要考虑数组中的所有元素。