【leetcode】1131. Maximum of Absolute Value Expression

题目如下：

Given two arrays of integers with equal lengths, return the maximum value of:

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

where the maximum is taken over all 0 <= i, j < arr1.length.

Example 1:
Input: arr1 = [1,2,3,4], arr2 = [-1,4,5,6]

Output: 13
Example 2:
Input: arr1 = [1,-2,-5,0,10], arr2 = [0,-2,-1,-7,-4]

Output: 20
Constraints:

2 <= arr1.length == arr2.length <= 40000

-10^6 <= arr1[i], arr2[i] <= 10^6

解题思路：对于表达式 |arr1[i] - arr1[j]| + |arr2[i] - arr2[j]| + |i - j|，在i < j的情况下，这个表达式的值是下面其中四个之一：

（arr1[i] + arr2[i] - i） - （arr1[j] + arr2[j] - j）

(arr1[i] - arr2[i] - i) - (arr1[j] - arr2[j] - j)

(arr2[i] - arr1[i] - i) - (arr2[j] - arr1[j] - j)

(arr2[i] + arr1[i] + i) - (arr2[j] + arr1[j] + j)

所以只要遍历一次数组，求出四个表达式中差值的最大值和最小值即可。

代码如下：

class Solution(object):

    def maxAbsValExpr(self, arr1, arr2):

        """

        :type arr1: List[int]

        :type arr2: List[int]

        :rtype: int

        """

        case_1_max = case_2_max = case_3_max = case_4_max = -float('inf')

        case_1_min = case_2_min = case_3_min = case_4_min = float('inf')

        for i in range(len(arr1)):

            case_1_max = max(case_1_max,arr1[i] + arr2[i] - i)

            case_1_min = min(case_1_min, arr1[i] + arr2[i] - i)

            case_2_max = max(case_2_max, arr1[i] - arr2[i] - i)

            case_2_min = min(case_2_min, arr1[i] - arr2[i] - i)

            case_3_max = max(case_3_max, arr2[i] - arr1[i] - i)

            case_3_min = min(case_3_min, arr2[i] - arr1[i] - i)

            case_4_max = max(case_4_max, arr2[i] + arr1[i] + i)

            case_4_min = min(case_4_min, arr2[i] + arr1[i] + i)

        return max(case_1_max - case_1_min,case_2_max - case_2_min,case_3_max - case_3_min,case_4_max - case_4_min)

巴特西

【leetcode】1131. Maximum of Absolute Value Expression

最新文章

热门文章