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;
    }
};

LeetCode-1131 Maximum of Absolute Value Expression