Maximum Distance in Arrays

Posted on | Edited on | In | | Views:

624. Maximum Distance in Arrays

Given m arrays, and each array is sorted in ascending order. Now you can pick up two integers from two different arrays (each array picks one) and calculate the distance. We define the distance between two integers a and b to be their absolute difference |a-b|. Your task is to find the maximum distance.

给一个嵌套的数组, 里面至少有两个数组, 每个数组里面至少有一个数字. 每个数组都是排序好的. 求最大的数字里头最大的差值. 需要注意的是如果从一个数组里选了最大值, 那个最小值就不能从这个数组里面选择了.

例如:

[
    [0, 8],
    [2, 4]
]
max distance = 8 - 2 = 6

思路

这道题的思路是, 扫一遍数组, 记录下max, min和maxdiff. maxdiff 是 max - current[0] 和 current[-1] - min的较大值.

Code

1
2
3
4
5
6
7
8
9
10
11
12
def maxDistance(arrays):
    max_val = arrays[0][-1]
    min_val = arrays[0][0]
    maxdiff = -float('inf')

    i = 1
    while i < len(arrays):
        maxdiff = max(maxdiff, max_val - arrays[i][0], arrays[i][-1] - min_val)
        max_val = max(max_val, arrays[i][-1])
        min_val = min(min_val, arrays[i][0])
        i += 1
    return maxdiff

时间复杂度

$O(n)$