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.

Challenge:

o(n) time and O(k) memory

Example:

For array [1, 2, 7, 7, 8], moving window size k = 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 maximum 7;

then the window move one step forward.

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

then the window move one step forward again.

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

Solution:

We maintain a deque to solve this problem. When we enqueue number into deque, we have to remove any number from the deque, if it is in front of the number which is enqueueing and it is smaller than enqueueing number. This could guarantee the max number is always on the top of the deque.

At the beginning, we add k-1 numbers to deque. Then, we repeat following steps for each number:

1. add new number into deque

2. peek the first number on deque as the maximum

3. remove the current - k + 1 number out of the deque

Code:

public class Solution {
    /**
     * @param nums: A list of integers.
     * @return: The maximum number inside the window at each moving.
     */
    public ArrayList<Integer> maxSlidingWindow(int[] nums, int k) {
        ArrayList<Integer> res = new ArrayList<>();
        if (nums == null || k == 0 || nums.length == 0) {
            return res;
        }
        Deque<Integer> deque = new ArrayDeque<>();
        for (int i = 0; i < k - 1; i++) { 
            inQueue(nums[i], deque);
        }
        for (int i = k - 1; i < nums.length; i++) {
            inQueue(nums[i], deque);
            res.add(deque.peekFirst());
            outQueue(nums[i - k + 1], deque);
        }
        return res;
    }

    private void inQueue(int num, Deque<Integer> deque) {
        while (!deque.isEmpty() && deque.peekLast() < num) {
            deque.pollLast();
        }
        deque.offer(num);
    }

    private void outQueue(int num, Deque<Integer> deque) {
        if (deque.peekFirst() == num) {
            deque.pollFirst();
        }
    }
}