Given an arraynums, there is a sliding window of sizekwhich is moving from the very left of the array to the very right. You can only see theknumbers in the window. Each time the sliding window moves right by one position.

For example,
Givennums=[1,3,-1,-3,5,3,6,7], andk= 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 assumekis always valid, ie: 1 ≤ k ≤ input array's size for non-empty array.

the key is to use deque to maintain a descending order array, the last most is the max

public class Solution {
    class Item {
        int index;
        int val;
        public Item(int index,int val) {
            this.index = index;
            this.val = val;
        }
    }
    public int[] maxSlidingWindow(int[] nums, int k) {
        if (nums == null || nums.length == 0) {
            return new int[0];
        }

        if (k == 0) {
            return nums;
        }
        int[] result = new int[nums.length - (k - 1)];
        int j = 0;
        Deque<Item> deque = new LinkedList<Item>();

        for (int i = 0; i < nums.length; i++) {
            // to keep descending order
            while( !deque.isEmpty() && deque.peekFirst().val < nums[i]) {
                deque.pollFirst();
            }

            deque.offerFirst(new Item(i, nums[i]));

            if (i >= k - 1) {
                // time to check the max
                while(!deque.isEmpty() && i - deque.peekLast().index >= k) {
                    deque.pollLast();
                }

                result[j++] = deque.peekLast().val;
            }
        }

        return result;
    }
}