Sliding Window Maximum

Given an array of n integer with duplicate number, and a moving window(size k), move the window at each iteration from the start of the array, find the maximum number inside the window at each moving.

Example

For array[1, 2, 7, 7, 8], moving window sizek = 3. return[7, 7, 8]

At first the window is at the start of the array like this

[|1, 2, 7| ,7, 8], return the maximum7;

then the window move one step forward.

[1, |2, 7 ,7|, 8], return the maximum7;

then the window move one step forward again.

[1, 2, |7, 7, 8|], return the maximum8;

Solution: Use a Deque. When larger number come, we poll the smaller number first. In this case, the maximum number should also at first position.

public ArrayList<Integer> maxSlidingWindow(int[] nums, int k) {
    ArrayList<Integer> res = new ArrayList<Integer>();
    if(nums == null || nums.length == 0) {
        return res;
    }
    Deque<Integer> deque = new ArrayDeque<Integer>();
    for(int i = 0; i < nums.length; i++) {
        if(i < k - 1) {
            inQueue(deque, nums[i]);
        }
        else if(i >= k - 1) {
            inQueue(deque, nums[i]);
            res.add(deque.peekFirst());
            if(nums[i - k + 1] == deque.peekFirst()) {
                deque.pollFirst();
            }
        }
    }
    return res;
}
public void inQueue(Deque<Integer> deque, int num) {
    while(!deque.isEmpty() && num > deque.peekLast()) {
        deque.pollLast();
    }
    deque.addLast(num);
}