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

原题链接：

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

https://leetcode.cn/problems/maximum-of-absolute-value-expression/description/

完成情况：

解题思路：

求方向

一次遍历两度统计

参考代码：

求方向

package 西湖算法题解___中等题02;

public class __1131绝对值表达式的最大值__计算曼哈顿距离__求方向导数 {
	int [][] dirs = {{1,1,1},{-1,1,1},{-1,-1,1},{1,-1,1},{1,1,-1},{-1,1,-1},{-1,-1,-1},{1,-1,-1}};  //定义出八种abs拆解情况
	/**
	 *
	 * @param arr1
	 * @param arr2
	 * @return
	 */
	public int maxAbsValExpr(int[] arr1, int[] arr2) {
		int maxValue = 0;
		int n = arr1.length;
		for (int [] dir:dirs){  //选择其中的某一个方向
			//定义最大值，最小值出来，进行方向判断的赋值
			int maxPoint = Integer.MIN_VALUE,minPoint  = Integer.MAX_VALUE;
			for (int i=0;i<n;i++){  //八个方向全部去进行统计，然后得出在某点出会得到的最大值
				maxPoint = Math.max(maxPoint,arr1[i]*dir[0] + arr2[i]*dir[1] + i*dir[2]);
				minPoint = Math.min(minPoint,arr1[i]*dir[0] + arr2[i]*dir[1] + i*dir[2]);
			}
			maxValue = Math.max(maxValue,maxPoint-minPoint);
			//每个方向都去进行最大值的判断
		}
		return maxValue;
	}
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

一次遍历两度统计

package 西湖算法题解___中等题02;

public class __1131绝对值表达式的最大值__计算曼哈顿距离__一次遍历两度统计 {
	/**
	 通过拆解绝对值，然后去计算每一个点的情况，
	    即处于该点时，arr1[i]、arr2[i]、i三者任意拼接构成的最小值，最大值的情况

	 * @param arr1
	 * @param arr2
	 * @return
	 */
	public int maxAbsValExpr(int[] arr1, int[] arr2) {
		//一次遍历，用两个最大值max去进行统计。
		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)));
	}
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33