Sliding Window Maximum - lintcode

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;

Analysis

The brute force solution is using two nested loops, which has time complexity of O(n^2). A new data structure should be used here Deque, because it allows us to poll the items from both the front and the back of the queue. Each time a new number is added to the end of the queue, queue should be poll from the tail unless there is no number less than the new number. This ensure that the deque's front always contains the maximum number.

Solution

Deque<Integer> deque = new LinkedList<Integer>();

public void inQueue(int num){
    while(!deque.isEmpty() && deque.peekLast() < num){
        deque.pollLast();
    }
    deque.offer(num);
}

public void outQueue(int num){
    if (deque.peekFirst() == num){
        deque.pollFirst();
    }
}

public ArrayList<Integer> maxSlidingWindow(int[] nums, int k) {
    ArrayList<Integer> res = new ArrayList<Integer>();
    if (nums.length == 0){
        return res;
    }

    for (int i = 0; i < k - 1; i++){
        inQueue(nums[i]);
    }

    for (int i = k - 1; i < nums.length; i++){
        inQueue(nums[i]);
        res.add(deque.peekFirst());
        outQueue(nums[i - k + 1]);
    }

    return res;
}