-
Notifications
You must be signed in to change notification settings - Fork 1
/
maxWindowValue.java
66 lines (52 loc) · 1.18 KB
/
maxWindowValue.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
import java.util.PriorityQueue;
public class maxWindowValue {
public static void main(String args[]) {
int arr[] = {10,9,8,7,6,5,100};
int w = 3;
heihei cl = new heihei();
int B[] = cl.windowmax(arr, w);
for (int i : B)
System.out.print(i + " ");
System.out.println(" ");
}
}
class heihei {
private class pair implements Comparable<pair> {
public int value;
public int index;
public pair(int a, int b) {
this.value = a;
this.index = b;
}
public int compareTo(pair other) {
if (this.value > other.value)
return 1;
else if (this.value < other.value)
return -1;
else
return 0;
}
}
public int[] windowmax(int arr[], int w) {
if (arr.length - w + 1 <= 0)
return null;
PriorityQueue<pair> pq = new PriorityQueue<pair>();
int B[] = new int[arr.length - w + 1];
for (int i = 0; i < w; i++)
pq.offer(new pair(arr[i], i));
pair tmp;
int i;
for (i = w; i < arr.length; i++) {
tmp = pq.peek();
B[i - w] = tmp.value;
while(tmp.index <= i - w) {
pq.poll();
tmp = pq.peek();
}
pq.offer(new pair(arr[i], i));
}
// one more time here
B[i - w] = pq.peek().value;
return B;
}
}