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.

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?

Hint:

How about using a data structure such as deque (double-ended queue)?
The queue size need not be the same as the window’s size.
Remove redundant elements and the queue should store only elements that need to be considered.

 1 public class Solution {
 2     public int[] maxSlidingWindow(int[] nums, int k) {
 3         if (nums.length == 0) return new int[0]; 
 4         int len = nums.length-k+1;
 5         int[] res = new int[len];
 6         PriorityQueue<Integer> queue = new PriorityQueue<Integer>(k, new Comparator<Integer>() {
 7             public int compare(Integer a, Integer b) {
 8                 return b-a;
 9             }
10         });
11         int i=0;
12         for (; i<k; i++) {
13             queue.offer(nums[i]);
14         }
15         res[0] = queue.peek();
16         int index = 1;
17         for (i=k; i<=nums.length-1; i++) {
18             if (queue.size() == k) {
19                 queue.remove(nums[i-k]);
20             }
21             queue.offer(nums[i]);
22             res[index++] = queue.peek();
23         }
24         return res;
25     }
26 }

 1 public class Solution {
 2     public int[] maxSlidingWindow(int[] nums, int k) {
 3         // Given nums = [1,3,-1,-3,5,3,6,7], and k = 3.
 4         if(k==0) return new int[0];
 5         
 6         LinkedList<Integer> q = new LinkedList<Integer>();
 7 
 8         int[] res = new int[nums.length-k+1];
 9         
10         for(int i=0; i<nums.length; i++) {
11             while(!q.isEmpty() && nums[i]>=nums[q.getLast()]){
12                 q.removeLast();
13             }
14             q.addLast(i);
15             
16             if(i-q.getFirst()+1 > k) {
17                 q.removeFirst();
18             }
19             if(i+1>=k) res[i-k+1] = nums[q.getFirst()];
20         }
21         
22         return res;
23     }
24 }