本题解采用了数学变换的思路。首先,将原表达式的绝对值拆解为四种情况:(arr1[i] + arr2[i] + i) - (arr1[j] + arr2[j] + j),(arr1[i] - arr2[i] + i) - (arr1[j] - arr2[j] + j),(arr1[i] - arr2[i] - i) - (arr1[j] - arr2[j] - j),(arr1[i] + arr2[i] - i) - (arr1[j] + arr2[j] - j)。对于每种情况,由于 arr1 和 arr2 的长度相等,可以遍历数组,将对应的表达式值存入四个数组 A, B, C, D 中。最后,分别计算这四个数组的最大值和最小值之差,取四者中的最大值作为结果。
时间复杂度: O(n)
空间复杂度: O(n)
class Solution:
def maxAbsValExpr(self, arr1: List[int], arr2: List[int]) -> int:
A, B, C, D = [], [], [], []
for i in range(len(arr1)):
A.append(arr1[i] + arr2[i] + i) # 对应表达式的第一种情况
B.append(arr1[i] - arr2[i] + i) # 对应表达式的第二种情况
C.append(arr1[i] - arr2[i] - i) # 对应表达式的第三种情况
D.append(arr1[i] + arr2[i] - i) # 对应表达式的第四种情况
a = max(A) - min(A)
b = max(B) - min(B)
c = max(C) - min(C)
d = max(D) - min(D)
return max(a, b, c, d) # 返回四种情况中的最大值