[编程题] 最大的LeftMax与rightMax之差绝对值
给定一个长度为N的整型数组arr，可以划分成左右两个部分： 左部分arr[0..K]，右部分arr[K+1..arr.length-1]，K可以取值的范围是[0,arr.length-2] 求这么多划分方案中，左部分中的最大值减去右部分最大值的绝对值，最大是多少？ 例如： [2,7,3,1,1] 当左部分为[2,7]，右部分为[3,1,1]时，左部分中的最大值减去右部分最大值的绝对值为4; 当左部分为[2,7,3]，右部分为[1,1]时，左部分中的最大值减去右部分最大值的绝对值为6; 最后返回的结果为6。 注意：如果数组的长度为N，请尽量做到时间复杂度O(N)，额外空间复杂度O(1).
public class Solution {
public static int getMaxABSLeftAndRight(int[] arr) {
int res = Integer.MIN_VALUE;
for (int i = ; i != arr.length - ; i++) {
int maxLeft = Integer.MIN_VALUE;
for (int j = ; j != i + ; j++) {
maxLeft = Math.max(arr[j], maxLeft);
}
int maxRight = Integer.MIN_VALUE;
for (int j = i + ; j != arr.length; j++) {
maxRight = Math.max(arr[j], maxRight);
}
res = Math.max(Math.abs(maxLeft - maxRight), res);
}
return res;
}
public static int getMaxABSLeftAndRightBetter(int[] arr) {
int[] leftMaxArr = new int[arr.length];
leftMaxArr[] = arr[];
int[] rightMaxArr = new int[arr.length];
rightMaxArr[arr.length - ] = arr[arr.length - ];
for (int i = ; i != arr.length; i++) {
leftMaxArr[i] = Math.max(leftMaxArr[i - ], arr[i]);
}
for (int i = arr.length - ; i != -; i--) {
rightMaxArr[i] = Math.max(rightMaxArr[i + ], arr[i]);
}
int max = ;
for (int i = ; i != arr.length - ; i++) {
max = Math.max(max, Math.abs(leftMaxArr[i] - rightMaxArr[i + ]));
}
return max;
}
public static int getMaxABSLeftAndRightBest(int[] arr) {
int max = Integer.MIN_VALUE;
for (int i = ; i != arr.length; i++) {
max = Math.max(arr[i], max);
}
return max - Math.min(arr[], arr[arr.length - ]);
}
}
首先选出的左右两部分的那两个最大的数，其中一个肯定是整个数组中最大的数，它可能被分在左边或右边，假设它在左边的话，那么只需要使右边那部分的最大的数最小就行，这样就能得出答案。而右边那部分一定包含数组最右边那个数（k的边界条件），假设刚才已找出的整个数组中最大的数下标为k，最右边那个数的下标为len-1，假设在len-1前到k这段区间中的数都比vec[len-1]小，那么答案就是vec[k]-vec[len-1]，若果这段区间内有比vec[len-1]大的，那么就把它归入左边部分，这样子左边部分最大值还是vec[k]，而右边部分最大值还是vec[len-1]，所以这样子最终答案就是vec[k]-vec[len-1]。同理，当vec[k]在右边部分时可以得出答案为vec[k]-vec[0]，所以最终答案就是max( Max-vec[0], Max-vec[len-1] ) 了。