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.

Have you met this question in a real interview?

Yes

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;

维护一个单调递减的双端队列，储存数组下标在队列里，如果新元素比队尾元素大，则队尾元素不可能成为最大值，所以可以被移除出队列。那么随着窗口移动，如果队头元素移除了队头元素区域，则把队头元素移除出队列。最大值永远是队尾的元素

1. 通过维护一个双端队列（单调递增）保持在size k以内（窗口大小）
2. 时间复杂度 O(n), 空间复杂度O(k)

public class Solution {
    /*
     * @param nums: A list of integers
     * @param k: An integer
     * @return: The maximum number inside the window at each moving
     */
    public ArrayList<Integer> maxSlidingWindow(int[] nums, int k) {
        // write your code here
        ArrayList<Integer> ans = new ArrayList<Integer>();
        if (nums == null || nums.length == 0) {
            return ans;
        }

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

        for (int i = 0; i < nums.length; i++) {
            if (!deque.isEmpty() && deque.peekFirst() == i - k) {
                deque.pollFirst();
            }

            while (!deque.isEmpty() && nums[i] > nums[deque.peekLast()]) {
                deque.removeLast();
            }

            deque.offerLast(i);
            if (i >= k - 1) {
                ans.add(nums[deque.peek()]);
            }
        }
        return ans;

    }
};

1. 线段树/hashheap O(nlgn) 时间， O(n) 空间