Java O(n) time without Deque, A cool technique using Dynamic Programming.


  • 0
    S

    I have implemented a solution for the technique shown in this link. Look for the solution 2 given by Shashank Jain. Thanks!

    http://stackoverflow.com/questions/8031939/finding-maximum-for-every-window-of-size-k-in-an-array

    public class Solution {
        public int[] maxSlidingWindow(int[] nums, int k) {
    		if(nums == null || nums.length == 0) {
    			return new int[]{};
    		}
    
    		int length = nums.length;
    		int[] leftMax = new int[length];
    		int[] rightMax = new int[length];
    
    		leftMax[0] = nums[0];
    		rightMax[length - 1] = nums[length - 1];
    
    		for(int i = 1; i < length; ++i) {
    			leftMax[i] = (i % k == 0) ? nums[i] : Math.max(leftMax[i-1], nums[i]);
    			rightMax[length - 1 - i] = ((length - 1 - i) % k == 0) ? nums[length - 1 - i] : 
    				Math.max(rightMax[length - i],nums[length - 1 - i]);
    		}
    
    		int[] res = new int[length - k + 1];
    
    		for(int i = 0; i < length - k + 1; ++i) {
    			res[i] = Math.max(leftMax[i + k - 1], rightMax[i]);
    		}
    		return res;
    	}
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.