题目

有一个整型数组arr和一个大小为w的窗口从数组的最左边滑到最右边，窗口每次向右边滑一个位置。

例如，数组为[4,3,5,4,3,3,6,7]，窗口大小为3时:

[4 3 5] 4 3 3 6 7 　max = 5

4 [3 5 4] 3 3 6 7 　max = 5

4 3 [5 4 3] 3 6 7 　max = 5

4 3 5 [4 3 3] 6 7 　max = 4

4 3 5 4 [3 3 6] 7 　max = 6

4 3 5 4 3 [3 6 7] 　max = 7

如果数组长度为n,窗口大小为w，则一共产生n-w+1个窗口的最大值。
请实现一个函数。

input:整型数组arr,窗口大小为w。

out:一个长度为n-w+1的数组res,res[i]表示每一种窗口状态下的最大值。

上面的结果应该返回{5,5,5,4,6,7}

思路

假定数组长度为N，窗口大小为w，我们可以通过两层for循环完成O(NxW)的时间复杂度，这种方法比较简单不予简述。

本题有时间复杂度为O(n)的方法，只要记录了以前的值就可以完成，使用双端队列的方式，即可完成。现有一个双向队列名为qmax，在qmax中保存下标，在java中使用LinkedList可以完成双向队列的工作，在qmax的队头用来保存我们当前的最大值的坐标，当队头的下标等于i-w的时候，就过期，直接弹出,这也是我们的最大值。qmax插入的规则如下:

当我们遍历到数组的第i个元素的时候，有如下规则:

如果qmax为空，直接插入i。
如果qmax不为空，则获取qmax队尾的坐标，记为j。
如果a[j]>a[i],说明队尾的值比他数组大，则直接插入队列。
如果a[j]<=a[i]，需要把j从qmax弹出，然后会到第二步，再决定插入的策略。
过期计算:如果qmax队头的下标等于i-w，说明过期，直接弹出。
计算res值，当i-w>=0的时候就可以记录res的值了。

qmax在其中的责任是负责维护窗口为w的子数组的最大值更新。

代码

public static int[] getMaxWindow(int[] arr,int w){
        if (arr == null || arr.length < w || w < 1){
            return null;
        }
        LinkedList<Integer> qmax = new LinkedList<Integer>();//用来记录最大值的更新
        int[] res = new int[arr.length-w+1];//用来记录结果
        int index = 0;
        for (int i = 0; i < arr.length; i++) {
            //1到4步骤的过程
            while (!qmax.isEmpty() && arr[qmax.peekLast()] <= arr[i]){
                qmax.pollLast();
            }
            qmax.addLast(i);

            //第5步:过期计算
            if (qmax.peekFirst() == i-w){
                qmax.pollFirst();
            }
            //第6步:记录res值
            if (i-w >= -1){
                res[index++]=arr[qmax.peekFirst()];
            }
        }
        return res;
    }

    public static void main(String[] args) {
        int[] arr = new int[]{4,3,5,4,3,3,6,7};
        int[] res = getMaxWindow(arr,3);
        for(int r : res){
            System.out.println(r);
        }
    }