-
-
Notifications
You must be signed in to change notification settings - Fork 299
/
962.java
86 lines (67 loc) · 2.5 KB
/
962.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
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
__________________________________________________________________________________________________
sample 3 ms submission
class Solution {
public int maxWidthRamp(int[] A) {
int n = A.length;
if(n==0){
return 0;
}
int[] leftCandidate = new int[n]; // all "possible" left indexes
int[] rightCandidate = new int[n]; // all "possible" right indexes
int currentLeft = 50001; // all elements in the range [0,50_000]. We want to ensure considering index = 0
int counter1 = 0;
for(int i=0;i<n;i++){
if(A[i]<currentLeft){
leftCandidate[counter1] = i;
currentLeft = A[i];
counter1++;
}
}
int n1 = counter1;
int counter2 = 0;
int currentRight = -1; // all elements in the range [0,50_000]. We want to ensure considering index = n-1.
for(int i =n-1;i>=0;i--){
if(A[i]>currentRight) {
rightCandidate[counter2] = i;
currentRight = A[i];
counter2++;
}
}
int n2 = counter2;
int maxSolution = 0;
int j = n2-1;
for(int i=0;i<n1;i++){
while(j >=0 && A[rightCandidate[j]]>=A[leftCandidate[i]]){
j--; // try to advance j
}
j++; // we advanced j one step one step "too much".
maxSolution = Math.max(maxSolution,rightCandidate[j]-leftCandidate[i]);
}
return maxSolution;
}
}
__________________________________________________________________________________________________
sample 46488 kb submission
class Solution {
public int maxWidthRamp(int[] A) {
if (A == null || A.length == 0) {
return 0;
}
Integer[] sortedIndices = new Integer[A.length];
for (int i = 0; i < A.length; i++) {
sortedIndices[i] = i;
}
Arrays.sort(sortedIndices, (i, j) -> ((Integer) A[i]).compareTo(A[j]));
for (int i = 0; i < A.length; i++) {
System.out.print(sortedIndices[i] + " ");
}
int min = sortedIndices[0];
int ramp = 0;
for (int i = 1; i < sortedIndices.length; i++) {
ramp = Math.max(ramp, sortedIndices[i] - min);
min = Math.min(min, sortedIndices[i]);
}
return ramp;
}
}
__________________________________________________________________________________________________