LeetCode-1131 Maximum of Absolute Value Expression

Description

给定两个数组 $a r r 1$ 和 $a r r 2$ ，求 $m a x {∣ a r r 1_{i} - a r r 1_{j} ∣ + ∣ a r r 2_{i} - a r r 2_{j} ∣ + ∣ i - j ∣}$

Constraints

时间复杂度不超过 $O (n)$

Solution

这道题就是求三维的曼哈顿距离，每一个点 $i$ 的坐标是 $(x_{i}, y_{i}, z_{i}) \to (a r r 1_{i}, a r r 2_{i}, i)$ 的形式

计算公式在未展开时为 $∣ Δ x ∣ + ∣ Δ y ∣ + ∣ Δ z ∣$

展开后为 $(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;
    }
};

Link

LeetCode-1131 Maximum of Absolute Value Expression