-
Notifications
You must be signed in to change notification settings - Fork 46
/
_962_1.java
56 lines (49 loc) · 1.68 KB
/
_962_1.java
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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
import java.util.AbstractMap;
import java.util.Map;
/**
* LeetCode 962 - Maximum Width Ramp
*
* Divide-and-Conquer approach
*/
public class _962_1 {
int inf = 1 << 29;
public int maxWidthRamp(int[] A) {
Map.Entry<Integer, Integer>[] entries = new Map.Entry[A.length];
for (int i = 0; i < A.length; i++) {
entries[i] = new AbstractMap.SimpleEntry(A[i], i);
}
int ans = dfs(entries, new Map.Entry[A.length], 0, A.length - 1);
return ans;
}
int dfs(Map.Entry<Integer, Integer>[] entries, Map.Entry<Integer, Integer>[] tmp, int left, int right) {
if (left >= right) {
return 0;
}
int ans = 0, mid = (left + right) / 2;
ans = Math.max(ans, dfs(entries, tmp, left, mid));
ans = Math.max(ans, dfs(entries, tmp, mid + 1, right));
int smallestIdx = inf;
int i = left;
int j = mid + 1;
int k = left;
while (i <= mid && j <= right) {
if (entries[i].getKey() <= entries[j].getKey()) {
smallestIdx = Math.min(smallestIdx, entries[i].getValue());
ans = Math.max(ans, entries[j].getValue() - smallestIdx);
tmp[k++] = entries[i++];
} else {
ans = Math.max(ans, entries[j].getValue() - smallestIdx);
tmp[k++] = entries[j++];
}
}
while (i <= mid) {
tmp[k++] = entries[i++];
}
while (j <= right) {
ans = Math.max(ans, entries[j].getValue() - smallestIdx);
tmp[k++] = entries[j++];
}
System.arraycopy(tmp, left, entries, left, right - left + 1);
return ans;
}
}