給定一個輸入二維陣列arrays。
請計算的陣列距離是多少?
陣列距離的定義 = max | a - b | 其中 a, b 來自不同的一維陣列
Example 1:
Input: arrays = [[1,2,3],[4,5],[1,2,3]]
Output: 4
Explanation:
Max distance = | 5 - 1 | = 4
Example 2:
Input: arrays = [[1],[1]]
Output: 0
Max distance = | 1 - 1 | = 0
Constraints:
m == arrays.length
輸入陣列長度 = m
2 <= m <= 10^5
m 介於 2 ~ 十萬之間。
1 <= arrays[i].length <= 500
內部的一維陣列長度介於1~500
-10^4 <= arrays[i][j] <= 10^4
每個陣列元素值介於 負一萬 ~ 正一萬
arrays[i]
is sorted in ascending order.內部的一維陣列都是升序排列。
10^5
integers in all the arrays.輸入裡面,最多會有十萬個整數。
distance = | a - b | 其中 a, b 來自不同的一維陣列
那就紀錄已經看過的最大值和最小值。
接著每回合針對當下的最小值和最大值做計算,取最大的差值。
候選人1: 已經看過的最大值 - 當下的最小值。
候選人2: 當下的最大值 -已經看過的最小值 。
接著更新distance 的最大值,選擇比較的大的那個候選人去做更新。
class Solution:
def maxDistance(self, arrays):
best = 0
# Initialization
cur_max, cur_min = -math.inf, math.inf
for numbers in arrays:
# Update max distance
best = max(best, cur_max - numbers[0], numbers[-1] - cur_min )
# Update max value before, min value before
cur_max, cur_min = max(cur_max, numbers[-1]), min(cur_min, numbers[0])
return best
依序處理每一個單獨的一維陣列,總共耗時O(n)。
所用到的變數都是臨時變數,所需空間為O(1)常數級別。