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
1.思考
- 一开始想到的是用二重循环将所有的组合都遍历一遍，该方法可行，但是复杂度太高，运行时间超时；
- 之后参考Discuss中方案进行编程，连接如下：
https://leetcode.com/problems/maximum-of-absolute-value-expression/discuss/340075/c%2B%2B-beats-100-(both-time-and-memory)-with-algorithm-and-image
2.实现
Runtime: 36ms(94.42%)
Memory: 12.3MB(100%)
/*
|arr1[i]-arr1[j]|+|arr2[i]-arr2[j]|+|i-j|
= (arr1[i]+arr2[j]+i)-(arr1[j]+arr2[j]+j)
= (arr1[i]+arr2[j]-i)-(arr1[j]+arr2[j]-j)
= (arr1[i]-arr2[j]+i)-(arr1[j]-arr2[j]+j)
= (arr1[i]-arr2[j]-i)-(arr1[j]-arr2[j]-j)
*/
class Solution {
public:
int maxAbsValExpr(vector<int>& arr1, vector<int>& arr2) {
int len = arr1.size();
vector<int> a1(len),a2(len),a3(len),a4(len);
for(int i=0; i<len; i++){
a1[i] = arr1[i]+arr2[i]+i;
a2[i] = arr1[i]+arr2[i]-i;
a3[i] = arr1[i]-arr2[i]+i;
a4[i] = arr1[i]-arr2[i]-i;
}
vector<int> res(4);
res[0] = *max_element(a1.begin(), a1.end()) - *min_element(a1.begin(), a1.end());
res[1] = *max_element(a2.begin(), a2.end()) - *min_element(a2.begin(), a2.end());
res[2] = *max_element(a3.begin(), a3.end()) - *min_element(a3.begin(), a3.end());
res[3] = *max_element(a4.begin(), a4.end()) - *min_element(a4.begin(), a4.end());
int r = *max_element(res.begin(), res.end());
return r;
}
};