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.

Code

public class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        if (nums==null || k<=0) return new int[0];
        int len = nums.length;
        int[] res = new int[len-k+1];
        int index = 0;
        Deque<Integer> dq = new ArrayDeque<Integer>();

        for(int i=0; i<len; i++){
            //dq里只能放从i开始往前k窗口的index，再往前的都要删掉
            while (!dq.isEmpty() && dq.peek() < i-k+1){
                dq.poll();
            }
            //从尾开始，把比nums[i]小的值都删掉，应为这些值又小，又在前面，以后都不可能会是最大值了
            while (!dq.isEmpty() && nums[dq.peekLast()]<nums[i]){
                dq.pollLast();
            }
            //前面的两步保证：
            //1. 所有的dequeue里的index都在window里
            //2. 最大值的index一定是dequeue的最前面（因为每次加一个大的，都把前面比它小的删掉了）
            dq.offer(i);
            //一旦i超过了k的长度，每次把dq最前面的放到答案里去
            if(i>=k-1){
                res[index++]=nums[dq.peek()];
            }
        }

        return res;
    }
}

Reference

• Leetcode