Medium

题目描述

给你两个长度相等的整数数组，返回下面表达式的最大值：

|arr1[i] - arr1[j]| + |arr2[i] - arr2[j]| + |i - j|

其中最大值是在满足 0 <= i, j < arr1.length 的所有 i 和 j 上取得的。

示例 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

提示：

  • 使用 abs(A) + abs(B) = max(A+B, A-B, -A+B, -A-B) 的思想。

解题思路

这道题的关键在于利用绝对值的性质来化简表达式。对于 |arr1[i] - arr1[j]| + |arr2[i] - arr2[j]| + |i - j|，我们需要巧妙地处理绝对值。

根据提示，对于任意两个数 A 和 B，有：|A| + |B| = max(A+B, A-B, -A+B, -A-B)

设 A = arr1[i] - arr1[j]，B = arr2[i] - arr2[j]，C = i - j

那么原表达式变为：|A| + |B| + |C|

由于 i 和 j 的大小关系确定了 C 的符号，我们可以分情况讨论：

  1. 当 i > j 时，C = i - j > 0
  2. 当 i < j 时，C = i - j < 0

对于每种情况，我们应用绝对值公式：|A| + |B| = max(A+B, A-B, -A+B, -A-B)

这样原问题转化为求四个表达式的最大值：

  • (arr1[i] + arr2[i] + i) - (arr1[j] + arr2[j] + j)
  • (arr1[i] - arr2[i] + i) - (arr1[j] - arr2[j] + j)
  • (-arr1[i] + arr2[i] + i) - (-arr1[j] + arr2[j] + j)
  • (-arr1[i] - arr2[i] + i) - (-arr1[j] - arr2[j] + j)

对于每个表达式，我们只需要找到对应组合的最大值和最小值，它们的差就是该表达式的最大值。

代码实现

class Solution {
public:
    int maxAbsValExpr(vector<int>& arr1, vector<int>& arr2) {
        int n = arr1.size();
        
        // 四种组合的最大值和最小值
        int max1 = INT_MIN, min1 = INT_MAX;  // arr1[i] + arr2[i] + i
        int max2 = INT_MIN, min2 = INT_MAX;  // arr1[i] - arr2[i] + i
        int max3 = INT_MIN, min3 = INT_MAX;  // -arr1[i] + arr2[i] + i
        int max4 = INT_MIN, min4 = INT_MAX;  // -arr1[i] - arr2[i] + i
        
        for (int i = 0; i < n; i++) {
            int val1 = arr1[i] + arr2[i] + i;
            int val2 = arr1[i] - arr2[i] + i;
            int val3 = -arr1[i] + arr2[i] + i;
            int val4 = -arr1[i] - arr2[i] + i;
            
            max1 = max(max1, val1); min1 = min(min1, val1);
            max2 = max(max2, val2); min2 = min(min2, val2);
            max3 = max(max3, val3); min3 = min(min3, val3);
            max4 = max(max4, val4); min4 = min(min4, val4);
        }
        
        return max({max1 - min1, max2 - min2, max3 - min3, max4 - min4});
    }
};

class Solution:
    def maxAbsValExpr(self, arr1: List[int], arr2: List[int]) -> int:
        n = len(arr1)
        
        # 四种组合的最大值和最小值
        max1 = min1 = arr1[0] + arr2[0] + 0
        max2 = min2 = arr1[0] - arr2[0] + 0
        max3 = min3 = -arr1[0] + arr2[0] + 0
        max4 = min4 = -arr1[0] - arr2[0] + 0
        
        for i in range(n):
            val1 = arr1[i] + arr2[i] + i
            val2 = arr1[i] - arr2[i] + i
            val3 = -arr1[i] + arr2[i] + i
            val4 = -arr1[i] - arr2[i] + i
            
            max1 = max(max1, val1)
            min1 = min(min1, val1)
            max2 = max(max2, val2)
            min2 = min(min2, val2)
            max3 = max(max3, val3)
            min3 = min(min3, val3)
            max4 = max(max4, val4)
            min4 = min(min4, val4)
        
        return max(max1 - min1, max2 - min2, max3 - min3, max4 - min4)

public class Solution {
    public int MaxAbsValExpr(int[] arr1, int[] arr2) {
        int n = arr1.Length;
        
        // 四种组合的最大值和最小值
        int max1 = int.MinValue, min1 = int.MaxValue;
        int max2 = int.MinValue, min2 = int.MaxValue;
        int max3 = int.MinValue, min3 = int.MaxValue;
        int max4 = int.MinValue, min4 = int.MaxValue;
        
        for (int i = 0; i < n; i++) {
            int val1 = arr1[i] + arr2[i] + i;
            int val2 = arr1[i] - arr2[i] + i;
            int val3 = -arr1[i] + arr2[i] + i;
            int val4 = -arr1[i] - arr2[i] + i;
            
            max1 = Math.Max(max1, val1);
            min1 = Math.Min(min1, val1);
            max2 = Math.Max(max2, val2);
            min2 = Math.Min(min2, val2);
            max3 = Math.Max(max3, val3);
            min3 = Math.Min(min3, val3);
            max4 = Math.Max(max4, val4);
            min4 = Math.Min(min4, val4);
        }
        
        return Math.Max(Math.Max(max1 - min1, max2 - min2), 
                       Math.Max(max3 - min3, max4 - min4));
    }
}

var maxAbsValExpr = function(arr1, arr2) {
    const n = arr1.length;
    
    // 四种组合的最大值和最小值
    let max1 = -Infinity, min1 = Infinity;
    let max2 = -Infinity, min2 = Infinity;
    let max3 = -Infinity, min3 = Infinity;
    let max4 = -Infinity, min4 = Infinity;
    
    for (let i = 0; i < n; i++) {
        const val1 = arr1[i] + arr2[i] + i;
        const val2 = arr1[i] - arr2[i] + i;
        const val3 = -arr1[i] + arr2[i] + i;
        const val4 = -arr1[i] - arr2[i] + i;
        
        max1 = Math.max(max1, val1);
        min1 = Math.min(min1, val1);
        max2 = Math.max(max2, val2);
        min2 = Math.min(min2, val2);
        max3 = Math.max(max3, val3);
        min3 = Math.min(min3, val3);
        max4 = Math.max(max4, val4);
        min4 = Math.min(min4, val4);
    }
    
    return Math.max(max1 - min1, max2 - min2, max3 - min3, max4 - min4);
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度数值
时间复杂度O(n)
空间复杂度O(1)