[LeetCode] 1131. Maximum of Absolute Value Expression

[grandyang]

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 和 arr2，让找出这个式子 |arr1[i] - arr1[j]| + |arr2[i] - arr2[j]| + |i - j| 的最大值。仔细观察这个式子，实际上是要找出两个坐标i和j，然后分别在两个数组中找出对应位置的数字，求差的绝对值并相加。存在绝对值的话就不太好求极值，需要去掉，那么就可能有正负两种情况，每个绝对值都有两种情况，这里三个绝对值号总共就有八种情况：

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

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

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

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

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

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

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

- arr1[i] + arr1[j] - arr2[i] + arr2[j] - i + 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[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[i] + arr2[i] + i) + (arr1[j] + arr2[j] + j)

仔细观察上面八种情况，其实后四种和前四种是重复的，因为i和j是可以交换的。这样的话我们只要找出前四种情况的最大值即可，为了最大化，就需要尽可能的最大化前面括号中的值，最小化后面括号的值。好就好在两个括号中的值的计算方法是相同的。若将括号内的整体看作某个数组中的下标为i的数字的话，那么就是数组中的最大值减去最小值。现在就要构建这四种不同的数组，构建方法也非常直接，就是根据括号中的内容，从 arr1 和 arr2 中各取一个i位置的数字，相加或相减，然后加上或减去坐标i即可，放到四个不同的数组中，然后分别算出它们的最大值减去最小值，取其中的最大值返回即可，参见代码如下：

class Solution {
public:
    int maxAbsValExpr(vector<int>& arr1, vector<int>& arr2) {
        int n = arr1.size();
        vector<int> sum1(n), sum2(n), diff1(n), diff2(n);
        for (int i = 0; i < n; ++i) {
            sum1[i] = arr1[i] + arr2[i] + i;
            sum2[i] = arr1[i] + arr2[i] - i;
            diff1[i] = arr1[i] - arr2[i] + i;
            diff2[i] = arr1[i] - arr2[i] - i;
        }
        return max(max(helper(sum1), helper(sum2)), max(helper(diff1), helper(diff2)));
    }
    int helper(vector<int>& arr) {
        int mx = arr[0], mn = arr[0];
        for (int num : arr) {
            mx = max(mx, num);
            mn = min(mn, num);
        }
        return mx - mn;
    }
};

Github 同步地址:

#1131

参考资料：

https://leetcode.com/problems/maximum-of-absolute-value-expression/

https://leetcode.com/problems/maximum-of-absolute-value-expression/discuss/339968/JavaC%2B%2BPython-Maximum-Manhattan-Distance

https://leetcode.com/problems/maximum-of-absolute-value-expression/discuss/340075/c%2B%2B-beats-100-(both-time-and-memory)-with-algorithm-and-image

LeetCode All in One 题目讲解汇总(持续更新中...)