题目描述

有一个整型数组arr和一个大小为w的窗口从数组的最左边划到最右边，窗口每次向右滑动一个位置 如数组为[4，5，8，2]，窗口大小为2时 [4 5] 8 2 最大值是5 4 [5 8] 2 最大值是8 4 5 [8 2] 最大值是8 数组长度为n窗口大小为w，则一共产生n-w+1个窗口最大值

输入：整型数组arr，窗口大小w输出：一个长度为n-w+1的数组res，res[i]表示每种窗口状态下的最大值，上例应返回[5, 8, 8]。

题目分析

可以先把初始窗口的最大值记录下来，每次向右移动一个位置，就看看最大的元素有没有被移除如果被移除了，则需要能找到第二大的元素，因此不能仅仅保存最大的数，用一个队列来保存，从头到尾按大小排列，新加入的元素需要按照大小给一个排位（事实上，原本队列中的比新元素小的元素可以被舍弃，因为他们本来就比新元素前，比新元素先排除，不会再新元素移除后成为次大的元素）。 那么队列应该保存什么数据呢，可以有两种：

保存具体最大的数值，如果移出的元素等于队头的元素，就把队头元素排除（会不会出现这种情况：队列中有小于当前队头，但是在当前队头前面的值，在这个值排出时，因为他不是队头，没有被比较排除，然后在后面成为队头？不会，队列中其他元素不会有比队头前的值，根据上面的条件，现在队头的这个值在入队时就把队列中小于他的值舍弃掉了，队列中比当前队头大的值又会在前面被排除）保存最大的数值的下标，如果队头元素位置已不在窗口则把队头排除

代码实现

方法一

public int[] getMax2(int[] array,int w){ if(array == null || w < 1 || w>array.length) return null; if(array.length == 0) return new int[0]; int [] ans = new int[array.length-w+1]; LinkedList<Integer> queue = new LinkedList<>(); int k = 0; for (int i = 0; i < array.length; i++) { while(!queue.isEmpty() && queue.peekLast()<array[i]){ queue.pollLast(); } queue.add(array[i]); if ( i >= w &&array[i - w] == queue.peek()){ queue.poll(); } if (i >= w-1) ans[k++] = queue.peek(); System.out.println(queue); } return ans; }

方法二

public int[] getMax(int[] array,int w){ if(array == null || w < 1 || w>array.length) return null; if(array.length == 0) return new int[0]; int [] ans = new int[array.length-w+1]; LinkedList<Integer> queue = new LinkedList<>(); int k = 0; for (int i = 0; i < array.length; i++) { while(!queue.isEmpty() && array[queue.peekLast()]<array[i]){ queue.pollLast(); } queue.add(i); if (i - w == queue.peek()){ queue.poll(); } if (i >= w-1) ans[k++] = array[queue.peek()]; } return ans; }