-
Notifications
You must be signed in to change notification settings - Fork 0
/
SlidingWindowMaximum.java
51 lines (38 loc) · 1.38 KB
/
SlidingWindowMaximum.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
class SlidingWindowMaximum {
int[][] sparse;
//matrix of size = nums.length x log(nums.length)
public int[] maxSlidingWindow(int[] nums, int k) {
int n = nums.length;
int c = log(n) + 1;
sparse = precompute(nums, n, c, k);
int[] ans = new int[n - k + 1];
for (int i = 0; i < n - k + 1; i++)
ans[i] = query(i, i + k - 1);
return ans;
}
//j=2 2^2=4
//2^1+2^1=2+2=4
public int[][] precompute(int[] nums, int n, int c, int k) {
int sparse[][] = new int[n][c];
for (int i = 0; i < n; i++)
sparse[i][0] = nums[i];
// (1 << j) = Math.pow(2, j)
// j = 2 -> 2^2 = 4 -> 2^1 + 2^1 = 2 + 2 = 4
for (int j = 1; (1 << j) <= n; j++) {
for (int i = 0; i + (1 << j) - 1 < n; i++) {
sparse[i][j] = Math.max(sparse[i][j - 1],
sparse[i + (1 << (j - 1))][j - 1]);
}
}
return sparse;
}
public int query(int low, int high) {
int l = high - low + 1;
int k = log(l);
return Math.max(sparse[low][k],
sparse[low + l - (1 << k)][k]);
}
public int log(int n){
return (int) (Math.log(n) / Math.log(2));
}
}