滑动窗口算法

给定一个数组和滑动窗口的大小，找出所有滑动窗口里数值的最大值。例如，如果输入数组{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]}。

思想：构建一个双端队列，begin为窗口左边界，队头为当前窗口的最大数值，每次滑动一次，则把新加的数值加入队尾并进行比较，如果大于前一个数，则弹出，则到队列为空或者数值比当前数值小，并且，每次获取队列时，应该比较当前的begin与队列头的数值的位置，查看队列数值是否过期，保证数值在当前的窗口里面。

画图分析

一开始时，begin应从-2开始（判断条件为begin大于等于0时开始获取最大值，这样可以保证第一次窗口有3个数值），此时窗口内有一个值为2，把下标写入队列；

​     

begin 右滑动，此时滑动窗口进入新的数字，从队尾开始比较，3比2大，则把 队列中的下标0弹出，此时队列为空，把3的下标1压入，此时判断begin与queue.peek()大小，可知没有过期，但是由于begin小于0，不做弹出操作

窗口滑动，此时按照步骤，弹出3的下标1，并把4的下标2压入队尾，此时 2>begin,所以没有过期，且begin=0，从此时开始，开始了获取最大值的操作，获取队头，则为当前最大值

按照这个步骤，逐步求值

代码

//num 为输入的数组  size 为滑动窗口大小

publicArrayList<Integer>maxInWindows(int[]num,intsize)

   {

ArrayList<Integer>list=newArrayList<Integer>();

if(size==0)returnlist;

ArrayDeque<Integer>queue=newArrayDeque<>();

intbegin;

for(inti=0;i<num.length;i++){

begin=i-size+1;//从-2开始

if(queue.isEmpty()){

queue.add(i);

       }

elseif(begin>queue.peekFirst()){//判断下标是否过期

    queue.pollFirst();

       }

while(!queue.isEmpty()&&num[queue.peekLast()]<=num[i]){//判断当前值的大小情况

queue.pollLast();

       }

queue.add(i);

if(begin>=0){

list.add(num[queue.peekFirst()]);

       }

     }

returnlist;

   }

}