[編程題] 最大的LeftMax與rightMax之差絕對(duì)值
給定一個(gè)長(zhǎng)度為N的整型數(shù)組arr，可以劃分成左右兩個(gè)部分： 左部分arr[0..K]，右部分arr[K+1..arr.length-1]，K可以取值的范圍是[0,arr.length-2] 求這么多劃分方案中，左部分中的最大值減去右部分最大值的絕對(duì)值，最大是多少？ 例如： [2,7,3,1,1] 當(dāng)左部分為[2,7]，右部分為[3,1,1]時(shí)，左部分中的最大值減去右部分最大值的絕對(duì)值為4; 當(dāng)左部分為[2,7,3]，右部分為[1,1]時(shí)，左部分中的最大值減去右部分最大值的絕對(duì)值為6; 最后返回的結(jié)果為6。 注意：如果數(shù)組的長(zhǎng)度為N，請(qǐng)盡量做到時(shí)間復(fù)雜度O(N)，額外空間復(fù)雜度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
}
首先選出的左右兩部分的那兩個(gè)最大的數(shù)，其中一個(gè)肯定是整個(gè)數(shù)組中最大的數(shù)，它可能被分在左邊或右邊，假設(shè)它在左邊的話，那么只需要使右邊那部分的最大的數(shù)最小就行，這樣就能得出答案。而右邊那部分一定包含數(shù)組最右邊那個(gè)數(shù)（k的邊界條件），假設(shè)剛才已找出的整個(gè)數(shù)組中最大的數(shù)下標(biāo)為k，最右邊那個(gè)數(shù)的下標(biāo)為len-1，假設(shè)在len-1前到k這段區(qū)間中的數(shù)都比vec[len-1]小，那么答案就是vec[k]-vec[len-1]，若果這段區(qū)間內(nèi)有比vec[len-1]大的，那么就把它歸入左邊部分，這樣子左邊部分最大值還是vec[k]，而右邊部分最大值還是vec[len-1]，所以這樣子最終答案就是vec[k]-vec[len-1]。同理，當(dāng)vec[k]在右邊部分時(shí)可以得出答案為vec[k]-vec[0]，所以最終答案就是max( Max-vec[0], Max-vec[len-1] ) 了。
更多文章、技術(shù)交流、商務(wù)合作、聯(lián)系博主
微信掃碼或搜索：z360901061
微信掃一掃加我為好友
QQ號(hào)聯(lián)系： 360901061
您的支持是博主寫(xiě)作最大的動(dòng)力，如果您喜歡我的文章，感覺(jué)我的文章對(duì)您有幫助，請(qǐng)用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧，狠狠點(diǎn)擊下面給點(diǎn)支持吧，站長(zhǎng)非常感激您！手機(jī)微信長(zhǎng)按不能支付解決辦法：請(qǐng)將微信支付二維碼保存到相冊(cè)，切換到微信，然后點(diǎn)擊微信右上角掃一掃功能，選擇支付二維碼完成支付。
【本文對(duì)您有幫助就好】元
