239. 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.

For example,
Given nums = [1,3,-1,-3,5,3,6,7], and k = 3.

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

Therefore, return the max sliding window as [3,3,5,5,6,7].

Note: 
You may assume k is always valid, ie: 1 ≤ k ≤ input array's size for non-empty array.

Follow up:
Could you solve it in linear time?

Solution:

Brutal force, for a given window, get the maximum and assign to result array. It's very straightforward. I am not going to write the code.  Time complexity(O(n*k))

O(n) solution:

Use a deque to track all possible maixmum for next window and discard all unnecessary elements. 

Eg. 1,3,-1,-3,5,3,6,7

For first window, 1 is unnecessary element, because there is a bigger element after it. 

For the second window, all elements are useful because if we keep adding smaller elements to the window, all three of (3,-1,-3) may become the maximum. 

For the third window, only 5 is useful, because when we sliding the window to the right, -1, -3 will never become the maximum before they sliding out from the window.

So basically when a new element sliding into the window we check the if this element is bigger than the tail, if yes we remove tail until the element is smaller than the tail and we push the element to the tail. Everytime if an element is going to be slided out, we check if this element is the head of the deque, if yes, we remove the head. When index is bigger than the k, we assign result array with the deque's head element. Because it is the maximum of current window,

 if(nums==null ||nums.length==0) return nums;  
     if(k==1) return nums;  
     LinkedList<Integer> q=new LinkedList<Integer>();  
     int[] res=new int[nums.length-k+1];  
     for(int i=0;i<nums.length;i++){  
       while(!q.isEmpty() && nums[i]>q.peekLast()) q.pollLast();  
       q.offer(nums[i]);  
       if(i+1>=k){  
         if(nums[i+1-k]==q.peek()) res[i+1-k]=q.poll();  
         else res[i+1-k]=q.peek();  
       }  
     }  
     return res;  
   }