class Solution {
public:
int maxAbsValExpr(vector<int>& arr1, vector<int>& arr2) {
}
};
1131. 绝对值表达式的最大值
给你两个长度相等的整数数组，返回下面表达式的最大值：
|arr1[i] - arr1[j]| + |arr2[i] - arr2[j]| + |i - j|
其中下标 i，j 满足 0 <= i, j < arr1.length。
示例 1：
输入：arr1 = [1,2,3,4], arr2 = [-1,4,5,6] 输出：13
示例 2：
输入：arr1 = [1,-2,-5,0,10], arr2 = [0,-2,-1,-7,-4] 输出：20
提示：
2 <= arr1.length == arr2.length <= 40000-10^6 <= arr1[i], arr2[i] <= 10^6原站题解
cpp 解法, 执行用时: 72 ms, 内存消耗: 28.3 MB, 提交时间: 2023-09-22 10:44:15
// 三维曼哈顿距离
class Solution {
public:
const int MAX_N = 2e6;
int CORNER[8][3] = {
{0, 0, 0}, {0, 0, MAX_N}, {0, MAX_N, MAX_N}, {0, MAX_N, 0},
{MAX_N, 0, 0}, {MAX_N, 0, MAX_N}, {MAX_N, MAX_N, MAX_N}, {MAX_N, MAX_N, 0}};
int manhatten(int x1, int y1, int z1, int x2, int y2, int z2) {
return abs(x1 - x2) + abs(y1 - y2) + abs(z1 - z2);
}
int maxAbsValExpr(vector<int>& arr1, vector<int>& arr2) {
int N = arr1.size();
vector<vector<int> > d(8, vector<int>(N, 0));
for (int i = 0; i < 8; ++i) {
for (int j = 0; j < N; ++j) {
d[i][j] = manhatten(j, arr1[j] + MAX_N / 2, arr2[j] + MAX_N / 2, CORNER[i][0], CORNER[i][1], CORNER[i][2]);
}
}
int res = 0;
for (int i = 0; i < 8; ++i) {
int mx = *max_element(d[i].begin(), d[i].end());
int mn = *min_element(d[i].begin(), d[i].end());
res = max(res, mx - mn);
}
return res;
}
};
java 解法, 执行用时: 3 ms, 内存消耗: 52 MB, 提交时间: 2023-09-22 10:43:18
class Solution {
public int maxAbsValExpr(int[] arr1, int[] arr2) {
int[][] arrs = {{1,1},{1,-1},{-1,1},{-1,-1}};
int res = 0;
for(int[] arr: arrs){
int max = Integer.MIN_VALUE;
int min = Integer.MAX_VALUE;
for(int i =0; i<arr1.length; i++){
int result = arr1[i] * arr[0] + arr2[i] * arr[1] + i;
if(max < result){
max = result;
}
if(min > result){
min = result;
}
}
if(res < max - min){
res = max - min;
}
}
return res;
}
}
golang 解法, 执行用时: 36 ms, 内存消耗: 6.6 MB, 提交时间: 2023-09-22 10:43:00
func maxAbsValExpr(arr1 []int, arr2 []int) int {
arrs := [][2]int{{1, 1}, {1, -1}, {-1, 1}, {-1, -1}}
res := 0
for _, arr := range arrs[:] {
max := -0x80000000
min := 0x7fffffff
for i := 0; i < len(arr1); i++ {
sum := arr1[i]*arr[0] + arr2[i]*arr[1] + i
if max < sum {
max = sum
}
if min > sum {
min = sum
}
}
diff := max - min
if diff > res {
res = diff
}
}
return res
}
python3 解法, 执行用时: 72 ms, 内存消耗: 27.6 MB, 提交时间: 2023-09-22 10:41:42
class Solution:
# 暴力解法，超时
def maxAbsValExpr0(self, arr1: List[int], arr2: List[int]) -> int:
res = 0
for i in range(len(arr1)):
for j in range(len(arr2)):
res = max(res, abs(arr1[i] - arr1[j]) + abs(arr2[i] - arr2[j]) + abs(i - j))
return res
# 数学
def maxAbsValExpr(self, arr1: List[int], arr2: List[int]) -> int:
A, B, C, D= [], [], [], []
for i in range(len(arr1)):
x, y = arr1[i], arr2[i]
A.append(x + y + i)
B.append(x + y - i)
C.append(x - y + i)
D.append(x - y - i)
a = max(A) - min(A)
b = max(B) - min(B)
c = max(C) - min(C)
d = max(D) - min(D)
return max(a, b, c, d)