LeetCode: Sliding Window Maximum

/**
Given an array nums, there is a sliding window of size k which is moving from the very left of the array to the very right. You can only see the k numbers in the window. Each time the sliding window moves right by one position. Return the max sliding window.

Example:

Input: nums = [1,3,-1,-3,5,3,6,7], and k = 3
Output: [3,3,5,5,6,7]
Explanation:

Window position                Max
---------------               -----
[1  3  -1] -3  5  3  6  7       3
 1 [3  -1  -3] 5  3  6  7       3
 1  3 [-1  -3  5] 3  6  7       5
 1  3  -1 [-3  5  3] 6  7       5
 1  3  -1  -3 [5  3  6] 7       6
 1  3  -1  -3  5 [3  6  7]      7
Note:
You may assume k is always valid, 1 ≤ k ≤ input array's size for non-empty array.

Follow up:
Could you solve it in linear time?
*/

/**
Solution:

We scan the array from 0 to n-1, keep "promising" elements in the deque. The algorithm is amortized O(n) as each element is put and polled once.

At each i, we keep "promising" elements, which are potentially max number in window [i-(k-1),i] or any subsequent window. This means

If an element in the deque and it is out of i-(k-1), we discard them. We just need to poll from the head, as we are using a deque and elements are ordered as the sequence in the array

Now only those elements within [i-(k-1),i] are in the deque. We then discard elements smaller than a[i] from the tail. This is because if a[x] <a[i] and x<i, then a[x] has no chance to be the "max" in [i-(k-1),i], or any other subsequent window: a[i] would always be a better candidate.

As a result elements in the deque are ordered in both sequence in array and their value. At each step the head of the deque is the max element in [i-(k-1),i]
*/
import java.util.*;

public class SlidingWindowMaximum{
public static int[] maxSlidingWindow(int[] nums, int k) {
        if(k<=0 || nums==null || nums.length<1){
            return nums;
        }
//dq holds the index of the items
        Deque<Integer> dq = new ArrayDeque<Integer>();
        int[] res = new int[nums.length -k +1];
        int index = 0;
        for(int i=0;i<nums.length; i++){
            //remove the earlier elements that fall out of current window
            while(!dq.isEmpty() && dq.peek()< i-k+1){
                dq.poll();
            }
            //remove the elements at tail that are smaller than current element
            while(!dq.isEmpty() && nums[dq.peekLast()]<nums[i]){
                dq.pollLast();
            }
            //the max element of current window is in the head of the dq
//add the current index to dq
            dq.offer(i);
//if i is larger enough to make the window (when i<k the window is not formed)
            if(i>=k-1){
                res[index++] = nums[dq.peek()];
            }
        }
        return res;
}

public static void main(String args[]){
int[] nums = {1,3,-1,-3,5,3,6,7};
int k = 3;
System.out.println(Arrays.toString(maxSlidingWindow(nums, k)));
}
}