1131. 绝对值表达式的最大值

川长思鸟来 2023-10-04 18:56 56阅读 0赞

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

|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

## Python 解法 （暴力 + 数学） ##

第一种思路 - 暴力解  
分析：  
此题乍一看很简单，要求 |arr1\[i\] - arr1\[j\]| + |arr2\[i\] - arr2\[j\]| + |i - j|，直接上双重循环的暴力解即可，然而数据规模较大，结果超时。

class Solution(object):
        def maxAbsValExpr(self, arr1, arr2):
            """
            :type arr1: List[int]
            :type arr2: List[int]
            :rtype: 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

曼哈顿距离 Python3

解题思路：  
我们将 arr1 中的所有值看做平面上点的横坐标，将 arr2 中的所有值看做平面上点的纵坐标，那么表达式 |arr1\[i\] - arr1\[j\]| + |arr2\[i\] - arr2\[j\]| + |i - j|，前两项就可以看成是平面上两点的曼哈顿距离，整个式子就是要求两个点的曼哈顿距离与两个点索引差的和。

由于有取绝对值的操作存在，那么可能产生的计算有 44 种，分别为：右上减左下，右下减左上，左上减右下，左下减右上。以测试样例为例，第一组样例如左图，右上减左下取得最大值为 3 + 7 + 3 = 13；第二组样例如右图，右下减左上取得最大值为 15 + 3 + 2 = 20。

所以我们枚举 44 种情况，分别求出每种情况中的最大值和最小值，然后做差更新答案即可。

class Solution:
        def maxAbsValExpr(self, arr1: List[int], arr2: List[int]) -> int:
            n = len(arr1)
            ans = 0
            # 枚举四个方向
            for dx, dy in [(1, 1), (-1, 1), (1, -1), (-1, -1)]:
                maxv = 0
                minv = 4000000
                # 计算当前方向上的曼哈顿距离最小值和最大值
                for i in range(n):
                    maxv = max(maxv, arr1[i] * dx + arr2[i] * dy + i)
                    minv = min(minv, arr1[i] * dx + arr2[i] * dy + i)
                # 更新答案
                ans = max(ans, maxv - minv)
            return ans

## java一次遍历 ##

解题思路  
对含有绝对值的式子求最大值，乍一看式子中含有两个下标i和j，好像需要来个双重for循环，但是一看题设条件，数组长度最大到40000，那显然双重for循环的brute force解法就行不通了，因此我们要换一个思路。

首先按照这么多年做数学题的经验来说，看到带有绝对值的式子，马上想到要消除绝对值。对于本题的式子，其中包含三个绝对值，每个绝对值能开出正反两种结果，因此带有三个绝对值的式子去掉绝对值后有8中可能性，如下图所示：

![eba7cb509cf007f2269e157fde1ec751.png][]

按照上图的分析，去绝对值号后将原本需要双重for循环的解法优化为只需要一次遍历数组即可，时间复杂度为O(n)，可以通过提交。对于A、B、C、D四个量在遍历数组的时候逐步计算其最大、最小值，即总共八个量，最后按照上图式子就可求出原问题的解。

class Solution {
        public int maxAbsValExpr(int[] arr1, int[] arr2) {
            int amin = Integer.MAX_VALUE, bmin = Integer.MAX_VALUE, cmin = Integer.MAX_VALUE, dmin = Integer.MAX_VALUE;
            int amax = Integer.MIN_VALUE, bmax = Integer.MIN_VALUE, cmax = Integer.MIN_VALUE, dmax = Integer.MIN_VALUE;
    
            for(int i = 0; i < arr1.length; i++) {
                amin = Math.min(amin, arr1[i]+arr2[i]+i);
                amax = Math.max(amax, arr1[i]+arr2[i]+i);
    
                bmin = Math.min(bmin, arr1[i]+arr2[i]-i);
                bmax = Math.max(bmax, arr1[i]+arr2[i]-i);
    
                cmin = Math.min(cmin, arr1[i]-arr2[i]+i);
                cmax = Math.max(cmax, arr1[i]-arr2[i]+i);
    
                dmin = Math.min(dmin, arr1[i]-arr2[i]-i);
                dmax = Math.max(dmax, arr1[i]-arr2[i]-i);
            }
    
            return Math.max(Math.max(amax-amin, bmax-bmin), Math.max(cmax-cmin, dmax-dmin));
        }
    }

[eba7cb509cf007f2269e157fde1ec751.png]: https://img-blog.csdnimg.cn/img_convert/eba7cb509cf007f2269e157fde1ec751.png