ORID56 max of sliding window

239. max of sliding window 解题报告
     这道题算经典了，因为很多笔试或者OA都会考到相关类型的题目。
     这道题就给你两个input， 一个数组，一个window size k (intput：int[] nums, int k)
     要输出的值就是每个window里面最大值组成的数组。
     那么首先要想到的就是先建立一个返回的数组，这个数组的大小应该是nums.length - k + 1

int[] res = new int[nums.length - k + 1];

用什么算法？

这道题实际上就是sliding window的一道题，sliding window本身就是一种解决问题的形式。不过这道题有一个很好地优化空间，你不必像sliding window本身那样每次把数组中的k个数取出来，然后存最大值，因为这样会导致时间复杂度变为O(NK)，而利口上面正好有一个很大的test case，所以会超时。
这道题能够节省时间复杂度的方式使用Deque，因为你可以在滑动窗口的时候直接把超出窗口空间的数字剔除，并且对比最后一个数字和即将放入队列的数字，如果比即将要进入队列的数字要小，那么就把最后一个数字去掉，这样deque里面第一个数就是当前最大的数。
而怎么保证你滑动窗口把超出窗口大小的数去掉？用deque来存index*
这是很重要的一步，因为如果你存的是数字，那就没法判断当前第一个数是否是超出窗口大小的index了。
一个比较重要的地方是deque在Java里面是通过ArrayDeque来实现的。
下面是代码

    public int[] maxSlidingWindow(int[] nums, int k) {
        if (nums == null) {
            return new int[0];
        }
        int[] res = new int[nums.length - k + 1];
        Deque<Integer> dq = new ArrayDeque<>();
        for (int i = 0; i < nums.length; i++) {
            if (!dq.isEmpty() && dq.peek() < i - k + 1) {
                dq.pollFirst();
            }
            while (!dq.isEmpty() && nums[dq.peekLast()] < nums[i]) {
                dq.pollLast();
            }
            dq.offer(i);
            if (i >= k-1) {
                res[i-k+1] = nums[dq.peek()];
            }
        }
        return res;
    }

时空复杂度

O（N）要走n次
O（K）deque的大小最大可能就是k，所以空间复杂度是k