題目
有一個整型數(shù)組 arr 和一個大小為 w 的窗口從數(shù)組的最左邊滑到最右邊,窗口每次向右邊滑一個位置堤尾。 返回一個長度為n-w+1的數(shù)組res良姆，res[i]表示每一種窗口狀態(tài)下的最大值趁冈。 以數(shù)組為[4,3,5,4,3,3,6,7]硅则，w=3為例怪瓶。因?yàn)榈谝粋€窗口[4,3,5]的最大值為5世蔗，第二個窗口[3,5,4]的最大值為5，第三個窗口[5,4,3]的最大值為5驼唱。第四個窗口[4,3,3]的最大值為4藻茂。第五個窗口[3,3,6]的最大值為6。第六個窗口[3,6,7]的最大值為7玫恳。所以最終返回[5,5,5,4,6,7]辨赐。
給定整形數(shù)組arr及它的大小n，同時給定w京办，請返回res數(shù)組掀序。保證w小于等于n，同時保證數(shù)組大小小于等于500惭婿。
測試樣例：[4,3,5,4,3,3,6,7],8,3
返回：[5,5,5,4,6,7]
思路
用雙端隊列deque保存可能成為滑動窗口中最大元素的下標(biāo)不恭，進(jìn)出隊列規(guī)則如下：
- 如果deque為空，直接將下標(biāo)i放入deque中财饥。
- 如果當(dāng)前下標(biāo)i-隊頭元素==w,彈出隊頭元素换吧。
- 如果deque不為空，取出deque隊尾的下標(biāo)j钥星，如果arr[j]>=arr[i],將下標(biāo)i放入deque隊尾沾瓦。否則依次彈出隊尾元素，直到arr[j]<arr[i]或者deque為空谦炒，再將i壓入隊尾贯莺。
1和2都比較好理解，這里解釋一下3:
如果arr[j]>=arr[i],將下標(biāo)i放入deque隊尾宁改。否則依次彈出隊尾元素缕探，直到arr[j]<arr[i]或者deque為空，再將i壓入隊尾.
arr[j]>=arr[i],為什么要放在隊尾呢还蹲，arr[i]雖然此時比arr[j]小爹耗，但是arr[j]會在一定時間后失效(即脫出滑動窗口范圍),arr[i]可能會成為最大值。
而當(dāng)arr[j]<arr[i],說明arr[j]永遠(yuǎn)不能成為當(dāng)前窗口及以后窗口的最大值了谜喊，因?yàn)閍rr[j]不僅比arr[i]小鲸沮，而且一定比arr[j]先失效。所以將其彈出即可锅论。
當(dāng)初始隊列構(gòu)造完成后讼溺，依次讀入數(shù)組元素，隊列的頭元素的下標(biāo)所代表的數(shù)字就是此時窗口中的最大值最易。
代碼
import java.util.*;
public class SlideWindow {
public int[] slide(int[] arr, int n, int w) {
int[]result=new int[n-w+1];
Deque<Integer> window=new ArrayDeque<>();
//初始化寬度為w的滑動窗口
int i=0;
for(;i<w;i++){
if(!window.isEmpty()&&arr[i]>arr[window.getLast()]){
while(!window.isEmpty()&&arr[window.getLast()]<arr[i]){
window.removeLast();
}
}
window.addLast(i);
}
int size=0;
result[size]=arr[window.getFirst()];
//依次進(jìn)行滑動
for(;i<n;i++){
if(i-window.getFirst()==w){
window.removeFirst();
}
if(!window.isEmpty()&&arr[i]>arr[window.getLast()]){
while(!window.isEmpty()&&arr[window.getLast()]<arr[i]){
window.removeLast();
}
}
window.addLast(i);
result[++size]=arr[window.getFirst()];
}
return result;
}
}
