Description
给定两个数组\(arr1\)和\(arr2\)，求\(max\{ \ \mid arr1_i - arr1_j \mid + \mid arr2_i - arr2_j \mid + \mid i - j \mid \ \}\)
Constraints
时间复杂度不超过\(O(n)\)
Solution
这道题就是求三维的曼哈顿距离，每一个点\(i\)的坐标是\((x_i, y_i, z_i) \to (arr1_i, arr2_i, i)\)的形式
计算公式在未展开时为\(\mid \Delta x \mid + \mid \Delta y \mid + \mid \Delta z \mid\)
展开后为\((A x_i + B x_j) + (C y_i + D y_j) + (E z_i + F z_j)\)，其中：
\[\begin{cases} A+B=0\\ C+D=0\\ E+F=0\\ A, B, C, D, E, F \in \{-1, 1\} \end{cases}\]因此，把\(\{A, C, E\}\)的8种情况列举出来就好处理了
每种情况的遍历过程可以算出\(A x_i + C y_i + E z_i\)和\(B x_j + D y_j + F z_j\)
Code
class Solution {
public:
int maxAbsValExpr(vector<int>& arr1, vector<int>& arr2) {
constexpr int d[][3] = {
{1, 1, 1},
{-1, 1, 1},
{1, -1, 1},
{1, 1, -1},
{-1, -1, 1},
{-1, 1, -1},
{1, -1, -1},
{-1, -1, -1}
};
int ans {};
for(auto &d : d) {
int mx {-1<<30}, mn {-mx};
for(int i = 0; i < arr1.size(); ++i) {
auto v = d[0] * arr1[i] + d[1] * arr2[i] + d[2] * i;
// {ACE}
mx = max(mx, v);
// -{BDF}
mn = min(mn, v);
}
// {ACE} + {BDF}
ans = max(ans, mx - mn);
}
return ans;
}
};