給定一個(gè)數(shù)組和滑動(dòng)窗口的大小垒探，找出所有滑動(dòng)窗口里數(shù)值的最大值跺株。例如宅楞，如果輸入數(shù)組{2,3,4,2,6,2,5,1}及滑動(dòng)窗口的大小3，那么一共存在6個(gè)滑動(dòng)窗口窗声，他們的最大值分別為{4,4,6,6,6,5}相恃； 針對(duì)數(shù)組{2,3,4,2,6,2,5,1}的滑動(dòng)窗口有以下6個(gè)： {[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]}揩魂。
思想：構(gòu)建一個(gè)雙端隊(duì)列，begin為窗口左邊界炮温，隊(duì)頭為當(dāng)前窗口的最大數(shù)值火脉，每次滑動(dòng)一次，則把新加的數(shù)值加入隊(duì)尾并進(jìn)行比較柒啤，如果大于前一個(gè)數(shù)倦挂，則彈出，則到隊(duì)列為空或者數(shù)值比當(dāng)前數(shù)值小担巩，并且方援，每次獲取隊(duì)列時(shí)，應(yīng)該比較當(dāng)前的begin與隊(duì)列頭的數(shù)值的位置涛癌，查看隊(duì)列數(shù)值是否過期犯戏，保證數(shù)值在當(dāng)前的窗口里面送火。
畫圖分析
一開始時(shí)，begin應(yīng)從-2開始（判斷條件為begin大于等于0時(shí)開始獲取最大值先匪，這樣可以保證第一次窗口有3個(gè)數(shù)值）种吸，此時(shí)窗口內(nèi)有一個(gè)值為2，把下標(biāo)寫入隊(duì)列呀非；
?? ? ?
begin 右滑動(dòng)坚俗，此時(shí)滑動(dòng)窗口進(jìn)入新的數(shù)字，從隊(duì)尾開始比較岸裙，3比2大猖败，則把 隊(duì)列中的下標(biāo)0彈出，此時(shí)隊(duì)列為空降允，把3的下標(biāo)1壓入恩闻，此時(shí)判斷begin與queue.peek()大小，可知沒有過期剧董，但是由于begin小于0判呕，不做彈出操作
窗口滑動(dòng)，此時(shí)按照步驟送滞，彈出3的下標(biāo)1侠草，并把4的下標(biāo)2壓入隊(duì)尾，此時(shí) 2>begin,所以沒有過期犁嗅，且begin=0边涕，從此時(shí)開始，開始了獲取最大值的操作褂微，獲取隊(duì)頭功蜓，則為當(dāng)前最大值
按照這個(gè)步驟，逐步求值
代碼
//num 為輸入的數(shù)組? size 為滑動(dòng)窗口大小
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()){//判斷下標(biāo)是否過期
? ? queue.pollFirst();
? ? ?? }
while(!queue.isEmpty()&&num[queue.peekLast()]<=num[i]){//判斷當(dāng)前值的大小情況
queue.pollLast();
? ? ?? }
queue.add(i);
if(begin>=0){
list.add(num[queue.peekFirst()]);
? ? ?? }
? ?? }
returnlist;
?? }
}
