239. Sliding Window Maximum

The basic idea is using deque to save candidate max value of current sliding window. For convenience, I take the deque as a stack in the following description:

1. At first, we initiate the sliding window by traversing the first k elements in nums, saving the index of candidate max value. Note that if nums[i] > nums[i - 1] then nums[i - 1] can't be the max element at any sliding window. Therefore, we can take the deque as a monotone decreasing stack and the max element of current sliding window is saved in the bottom of the stack.
2. After Initialization, we slide the window. If the bottom element of the stack is out of boundary of current window, pop it out. Then we compare the new element of the current window (the right most element of current window) with the top element of the stack to keep the stack montone decreasing.

Just remember, the max element of current window always lies in the bottom of the stack.

public int[] maxSlidingWindow(int[] nums, int k) {
    if( nums.length < 1 )
	return new int[0];
    int result[] = new int[nums.length - k + 1];
    Deque<Integer> q = new LinkedList<Integer>();
    for(int i = 0; i < k; i++) { // traverse the first k element to initiate the sliding window
	while( !q.isEmpty() && nums[i] > nums[q.peekLast()] )
	    q.pollLast();
        q.offerLast(i);
    }
    result[0] = nums[q.peekFirst()];
    for(int i = k; i < nums.length; i++){
	if( q.peekFirst() <= i - k )
	    q.pollFirst();
	while( !q.isEmpty() && nums[i] > nums[q.peekLast()] )
	    q.pollLast();
	q.offerLast(i);
	result[i - k + 1] = nums[q.peekFirst()];
    }
    return result;
}