Java solution using Deque and PriorityQueue


  • 0
    G
    public class Solution {
        public int[] maxSlidingWindow(int[] nums, int k) {
        	if (k > nums.length || nums == null) return null;     	
        	if (nums.length == 0 || k == 0) return nums;
        	Deque<Integer> window = new LinkedList<>();    	
        	List<Integer> maxList = new ArrayList<>(); 
        	PriorityQueue<NumValueIndex> p = new PriorityQueue<>(new Comparator<NumValueIndex>() {
        		@Override
        		public int compare(NumValueIndex o1, NumValueIndex o2) {
        			return o1.val.compareTo(o2.val) * -1;
        		}
    		});
        	int currMax = Integer.MIN_VALUE;
        	
        	// fill the 1st window
        	int i = 0;
        	for(i = 0; i < k; i++) {
        		window.add(nums[i]);
        		p.add(new NumValueIndex(i, nums[i]));
        		currMax = Math.max(currMax, nums[i]);    		
        	}
        	maxList.add(currMax);
        	    	
        	for (; i < nums.length; i++) {
    			int headElem = window.removeFirst();
    			window.add(nums[i]);
    			p.add(new NumValueIndex(i, nums[i]));
    			
        		if (headElem == currMax) {
        			while(p.peek().i < i - k + 1) {
        				p.poll();
        			}
        			currMax = p.peek().val;    			
        		} else {
        			currMax = Math.max(currMax, nums[i]);	
        		}
        		maxList.add(currMax);    		    		
    	}
            
        	int[] r = new int[maxList.size()];
        	i = 0;
        	for (Integer max : maxList) {
    		r[i++] = max;
    	}
        	return r;
        }
    }
    
    class NumValueIndex {
    	Integer i;
    	Integer val;
    	public NumValueIndex(int i, int val) {
    		super();
    		this.i = i;
    		this.val = val;
    	}	
    }
    

Log in to reply
 

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