[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][0] = 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]);
    }
}

Author: huadonghu

Leave a Reply

Your email address will not be published. Required fields are marked *