Description

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 maximum 8;

Solution

用双端队列，方法有：poll(), peek(), offer(), poolLast(), peekLast(), offerLast()
维持一个递减序列，保证最左边的数就是窗口中最大的数，这样随着窗口的移动如果最左边的数被拿掉了，那么接下来最大的数就是现在最左边的数。
什么时候从左边出队列- 队列不为空并且左边的index超出窗口的范围，所以deque里面存的应该是index
从右边入队列的时候，先把队列中所有比当前数小的数拿出去，以维持递减序列。

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) {
        // write your code here
        ArrayList<Integer> ret = new ArrayList<Integer>();
        if (nums == null || nums.length == 0 || nums.length < k) {
            return ret;
        }

        LinkedList<Integer> deque = new LinkedList<Integer>();
        for (int i = 0; i < nums.length; i++) {
            if (!deque.isEmpty() && i - k == deque.peek()) {
                deque.poll();
            }

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

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

        return ret;
    }
}