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;

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