题目描述： 给定一个数组和滑动窗口的大小，找出所有滑动窗口里数值的最大值。例如，如果输入数组{2,3,4,2,6,2,5,1}及滑动窗口的大小3，那么一共存在6个滑动窗口，他们的最大值分别为{4,4,6,6,6,5}； 针对数组{2,3,4,2,6,2,5,1}的滑动窗口有以下6个： {[2,3,4],2,6,2,5,1}， {2,[3,4,2],6,2,5,1}， {2,3,[4,2,6],2,5,1}， {2,3,4,[2,6,2],5,1}， {2,3,4,2,[6,2,5],1}， {2,3,4,2,6,[2,5,1]}。 题目分析： 这是一个使用双向队列，又称为单调双向链表，该结构中存储顺序必须是按照从大到小进行存储，每次将数组的下标记录在该双向队列中，数组下标意味着该元素的过期值，窗口中的最大值就是该队列中未过期的头元素对应的数值。若是在元素进入队列时有元素比前边元素大，那么将小于该元素的值全部从后边出队列，原因是当前的数值比前边的元素大而且过期时间晚。 （参考左神的算法双向队列） 代码如下：
import java.util.ArrayDeque; import java.util.ArrayList; public class Solution { public ArrayList<Integer> maxInWindows(int [] num, int size) { ArrayList<Integer> reslist=new ArrayList<Integer>(); //如果数组为空或者窗口小于0则返回空链表 if(num.length<=0||size>num.length||size<=0) { return reslist; } //定义一个左边指针，一个右边指针来表示窗口 int left=0; int right=0; ArrayDeque<Integer> que=new ArrayDeque<Integer>(size); que.add(0); //一次进行数组遍历便可以将元素的窗最值求的，时间复杂度O（N） for(right=0;right<num.length;) { //已经形成了窗口并且队列中的头结点没有过期 if(right-left+1==size&&que.getFirst()>=left) { fun(que,left,right,num); }else if(right-left+1==size&&que.getFirst()<left){ //已经形成了头结点并且头节点过期 que.pollFirst(); fun(que,left,right,num); }else { //还没有形成窗口 while(right-left+1!=size) { right++; fun(que,left,right,num); } } //每次将窗口中的最大元素存入链表中 reslist.add(num[que.getFirst()]); left++;right++; } return reslist; } public void fun(ArrayDeque<Integer> que,int left,int right,int[] num) { //如果当前的值比前面的值大，那么将前面小的数从队列中出列，再将新的最大值入列 while(!que.isEmpty()&&num[que.getLast()]<num[right]) { que.pollLast(); } que.addLast(right); } }