LeetCode 1131 最远曼哈顿距离

发表于

题目：给你两个长度相等的整数数组，返回下面表达式的最大值：

1
|arr1[i] - arr1[j]| + |arr2[i] - arr2[j]| + |i - j|

其中下标 i，j 满足 0 <= i, j < arr1.length。

思路：其实这道题的引申问题也就是求最远曼哈顿距离。而最远曼哈顿距离也可以引申为新增一个点，求该点到一群点的最大曼哈顿距离。

最大曼哈顿距离的求解方法：

1
2
3
4
|x1 - x2| + |y1 - y2| 
等价于 x1-x2 + y1-y2 (1,1), -x1+x2 + -y1+y2 (-1,-1), x1-x2 + -y1+y2 (1,-1), -x1+x2 + y1-y2 (-1,1) 
也就等价于 (x1,y1)-(x2,y2),(-(x1,y1))-(-(x2,y2)),(x1,-y1)-(x2,-y2),(-x1,y1)-(-x2,y2)
最后的最大距离的点，必然是位于这四种情况中的某一种，因此对于每种情况，保留其中的min坐标，对于新加入的点，若为最大，必然是减去min坐标
1
2
3
4
5
6
7
8
9
10
class Solution:
    def maxAbsValExpr(self, arr1: List[int], arr2: List[int]) -> int:
        res = 0
        for i, j in [[1, 1], [1, -1], [-1, -1], [-1, 1]]:
            close = arr1[0] * i + arr2[0] * j
            for k in range(1, len(arr1)):
                p = arr1[k] * i + arr2[k] * j + k
                res = max(res, p - close)
                close = min(close, p)
        return res

反思：这道题其实很有借鉴意义，因为之前面试的时候就遇到过这道题，结果没有做出来。原来就是四种情况，每次保存每种情况最小的那个坐标即可。