Deque based simple java solution that is clear to understand


  • 1

    So, this took me a while to understand, but i think that was mainly because some of the top rated answers were rather terse for my liking. I found this link very useful to visualize what's going on. Here's my (copied) version of the solution just annotated with some notes:

    	/**
    	 * Maintain a dequeue that will allow you to delete from the beginning and the end easily.
    	 * Inside this deque, store indices of the array (not the elements themselves!). Here's the
    	 * invariant that needs to be maintained:
    	 * 
    	 * The "start" of the deque must have the index pointing to the biggest element in the current window.
    	 * This way, it's easy to add the top of the deque (via peek) to the result.
    	 * 
    	 * Any new element being considered should be compared to all elements in the deque. If it's larger,
    	 * then we delete everything from the tail and insert it.
    	 * 
    	 * @param nums
    	 * @param k
    	 * @return
    	 */
        public int[] maxSlidingWindow(int[] nums, int k) {
            
            if (nums == null || nums.length == 0) return nums;
            int[] res = new int[nums.length - k + 1];
            Deque<Integer> queue = new ArrayDeque<>();
            for (int i = 0; i < nums.length; i++) {
            	int currIndex = i - k + 1;
    		if (currIndex >= 1) { // only once the currIndex is >= 1 should be consider trimming "old" indices
    	        	// Purge old indices if they exist in the queue
    			while (!queue.isEmpty() && queue.peekFirst() < currIndex) {
    				queue.pollFirst();
    			}
    		}
            	// keep the index pointing to the biggest element at the tail
            	while (!queue.isEmpty() && nums[i] > nums[queue.peekLast()]) {
            		queue.pollLast();
            	}        	
            	queue.addLast(i);
            	if (currIndex >= 0) {
            		res[currIndex] = nums[queue.peek()];
            	}
            }
            return res;	
        }
    

Log in to reply
 

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