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 和 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 同步地址:

https://github.com/grandyang/leetcode/issues/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 题目讲解汇总(持续更新中…)


转载请注明来源于 Grandyang 的博客 (grandyang.com),欢迎对文章中的引用来源进行考证,欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论,也可以邮件至 grandyang@qq.com

💰


微信打赏


Venmo 打赏

×

Help us with donation