滑动窗口问题

问题：

image.png

补充：

用一个双端链表，保证头部一直是当前的最大值，双端链表，左边是头部，右边是尾部，保证从头部到尾部是严格降序的也就是头部的数一定是最大的。当链表不为空且加入的数比当前链表最后一个尾部的数大的时候，弹出尾部，如果一直大就一直弹。然后加入当前数，当最头部的数失效时，就是窗口向前移动，移出头部下标时候，弹出来。如果还没到当前窗口大小，就一直往里加数，如果到了窗口大小就开始向结果里加当前数的最大值。
牛客初级课第八章。

首先，补充一下滑动窗口的基本思路，定义两个变量l，r（l,r只能向右移动），来标示一个窗口的大小，然后用一个双端队列（首部和尾部都能够加或者弹出）来存储，在原数组中的下标的位置，具体过程如下
比如一组数组 2，5，4，6 ，起始时候l,r都是0，双端队列为空，当r向右移动时，窗口大小为1，此时就是[2],5,4,6；此时双端队列里加入2的下标0；下一步r再向右移动一步，此时窗口里是[2,5],4,6；这时双端队列加入5的下标1，再加入一个比当前队列里数大的数的时候，要先把原队列里的数弹出，然后再加当前数，比如原队列里右2，要先把2弹出，再加入5的下标，这一步执行完后，双端队列里的值是1；r再向右移动1位，此时数组是[2,5,4],6，双端队列因为5>4，所以4的下标直接加入到队列里，双端队列里的数是 1，2；此时如果l向左移动一步，数组编程了2，[5,4]，6，这时看由于窗口移动而出窗口的2在双端队列里有没有失效，因为双端队列里本来就不包含2的下标所以无影响，依次执行下去即可。
这种方法是求窗口里的最大值，双端队列是头大尾小，即从前到后递减的双端队列，如果求窗口最小值就相反。注意双端队列里存储的数组的下标
以上就是处理滑动窗口的原理

思路：

利用滑动窗口的原理，本题窗口大小已经确定，即不存在l，r，直接利用原理计算即可

代码：

public static int[] getMaxWindow(int[] arr, int w) {
        if (arr == null || w < 1 || arr.length < w) {
            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++) {
                        //当队列不是空且入队列的数大于原队列的最后一个数
            while (!qmax.isEmpty() && arr[qmax.peekLast()] <= arr[i]) {
                qmax.pollLast();
            }
            qmax.addLast(i);
                        //当窗口向右移动，原来在窗口中的最左端数字失效了比如1234，w=3，移动到了4，3-3=0，所以下标为0的就失效，退出队列
            if (qmax.peekFirst() == i - w) {
                qmax.pollFirst();
            }
                        //当i大于等于窗口大小时才开始计算窗口里的最大值
            if (i >= w - 1) {
                res[index++] = arr[qmax.peekFirst()];
            }
        }
        return res;
    }

    // for test
    public static void printArray(int[] arr) {
        for (int i = 0; i != arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
        System.out.println();
    }

    public static void main(String[] args) {
        int[] arr = { 4, 3, 5, 4, 3, 3, 6, 7 };
        int w = 3;
        printArray(getMaxWindow(arr, w));

    }