[编程题] 最大的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).
1
public
class
Solution {
2
3
public
static
int
getMaxABSLeftAndRight(
int
[] arr) {
4
int
res =
Integer.MIN_VALUE;
5
for
(
int
i =
0
; i != arr.length -
1
; i++
) {
6
int
maxLeft =
Integer.MIN_VALUE;
7
for
(
int
j =
0
; j != i +
1
; j++
) {
8
maxLeft =
Math.max(arr[j], maxLeft);
9
}
10
int
maxRight =
Integer.MIN_VALUE;
11
for
(
int
j = i +
1
; j != arr.length; j++
) {
12
maxRight =
Math.max(arr[j], maxRight);
13
}
14
res = Math.max(Math.abs(maxLeft -
maxRight), res);
15
}
16
return
res;
17
}
18
19
public
static
int
getMaxABSLeftAndRightBetter(
int
[] arr) {
20
int
[] leftMaxArr =
new
int
[arr.length];
21
leftMaxArr[
0
] = arr[
0
];
22
int
[] rightMaxArr =
new
int
[arr.length];
23
rightMaxArr[arr.length -
1
] = arr[arr.length -
1
];
24
for
(
int
i =
1
; i != arr.length; i++
) {
25
leftMaxArr[i] = Math.max(leftMaxArr[i -
1
], arr[i]);
26
}
27
for
(
int
i = arr.length -
2
; i != -
1
; i--
) {
28
rightMaxArr[i] = Math.max(rightMaxArr[i +
1
], arr[i]);
29
}
30
int
max =
0
;
31
for
(
int
i =
0
; i != arr.length -
1
; i++
) {
32
max = Math.max(max, Math.abs(leftMaxArr[i] - rightMaxArr[i +
1
]));
33
}
34
return
max;
35
}
36
37
public
static
int
getMaxABSLeftAndRightBest(
int
[] arr) {
38
int
max =
Integer.MIN_VALUE;
39
for
(
int
i =
0
; i != arr.length; i++
) {
40
max =
Math.max(arr[i], max);
41
}
42
return
max - Math.min(arr[
0
], arr[arr.length -
1
]);
43
}
44
45
}
首先选出的左右两部分的那两个最大的数，其中一个肯定是整个数组中最大的数，它可能被分在左边或右边，假设它在左边的话，那么只需要使右边那部分的最大的数最小就行，这样就能得出答案。而右边那部分一定包含数组最右边那个数（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] ) 了。
