Leetcode 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 1: Use TreeMap to store the window, the complexity is O(nlogk).

Solution 2: Use deque. When slide the window, remove all the element smaller then new element from right and remove element that pass the left window. The most left element of the deque is always the largest one of the window. Complexity is O(n).

 public class Solution {  
   public int[] maxSlidingWindow(int[] nums, int k) {  
     Deque<Integer> dq=new LinkedList<>();  
     int n=nums.length;  
     if (n==0 || k==0) return new int[0];  
     int[] res=new int[n-k+1];  
     for (int j=0; j<n; j++) {  
       while (!dq.isEmpty() && nums[dq.peekLast()]<=nums[j]) dq.pollLast();  
       dq.addLast(j);  
       if (j>=k-1) {  
         if (dq.peekFirst()<j-k+1) dq.pollFirst();  
         res[j-k+1]=nums[dq.peekFirst()];  
       }  
     }  
     return res;  
   }  
 }