# [LeetCode] 239. Sliding Window Maximum

## Solution

There are several approaches to solve this problem, like sliding window or DP. A more general description of this problem is how to quickly find a Maximum or Minimum between two indices in a fixed array? This kind of question is called RMQ (Range Minimum Query).

Given a fixed array A and two indices i ≤ j, what is the smallest element out of A[i], A[i + 1], …, A[j – 1], A[j]?

The following content is adopted from lectures from Stanford.

## Code

``````class Solution {
int N , M ;
int[][] dp;
int[] nums;
public int[] maxSlidingWindow(int[] nums, int k) {
this.nums = nums;
N = nums.length + 1;
M = (int) (Math.log(N) / Math.log(2)) + 1;
dp = new int[N][M];
prepare();
int[] ans = new int[nums.length - k + 1];
for(int i = 0; i + k <= nums.length; i++) {
ans[i] = query(i, i + k - 1);
}
return ans;
}

private void prepare() {
for(int i = 0; i < nums.length; i++) {
dp[i] = nums[i];
}
for (int j = 1; j < M; j++) {
for(int i = 0; i + (1 << j) - 1 <= nums.length; i++) {
dp[i][j] = Math.max(dp[i][j-1], dp[i + (1 << (j - 1))][j-1]);
}
}
}

private int query(int l, int r) {
int k = (int) (Math.log(r - l + 1) / Math.log(2));
return Math.max(dp[l][k], dp[r - (1 << k) + 1][k]);
}
}``````  