題目
有一個整型數(shù)組arr和一個大小為w的窗口從數(shù)組的最左邊滑到最右邊，窗口每次向右邊滑一個位置。
例如所踊，數(shù)組為[4,3,5,4,3,3,6,7]辉哥，窗口大小為3時:
[4 3 5] 4 3 3 6 7 max = 5
4 [3 5 4] 3 3 6 7 max = 5
4 3 [5 4 3] 3 6 7 max = 5
4 3 5 [4 3 3] 6 7 max = 4
4 3 5 4 [3 3 6] 7 max = 6
4 3 5 4 3 [3 6 7] max = 7
如果數(shù)組長度為n,窗口大小為w，則一共產(chǎn)生n-w+1個窗口的最大值耳贬。
請實現(xiàn)一個函數(shù)踏堡。
input:整型數(shù)組arr,窗口大小為w。
out:一個長度為n-w+1的數(shù)組res,res[i]表示每一種窗口狀態(tài)下的最大值咒劲。
上面的結(jié)果應(yīng)該返回{5,5,5,4,6,7}
思路
假定數(shù)組長度為N顷蟆，窗口大小為w胖秒，我們可以通過兩層for循環(huán)完成O(NxW)的時間復(fù)雜度，這種方法比較簡單不予簡述慕的。
本題有時間復(fù)雜度為O(n)的方法阎肝，只要記錄了以前的值就可以完成，使用雙端隊列的方式肮街，即可完成》缣猓現(xiàn)有一個雙向隊列名為qmax，在qmax中保存下標(biāo)嫉父，在java中使用LinkedList可以完成雙向隊列的工作沛硅，在qmax的隊頭用來保存我們當(dāng)前的最大值的坐標(biāo)，當(dāng)隊頭的下標(biāo)等于i-w的時候绕辖，就過期摇肌，直接彈出,這也是我們的最大值。qmax插入的規(guī)則如下:
當(dāng)我們遍歷到數(shù)組的第i個元素的時候仪际，有如下規(guī)則:
- 如果qmax為空围小，直接插入i。
- 如果qmax不為空树碱，則獲取qmax隊尾的坐標(biāo)肯适，記為j。
- 如果a[j]>a[i],說明隊尾的值比他數(shù)組大成榜，則直接插入隊列框舔。
- 如果a[j]<=a[i]，需要把j從qmax彈出赎婚，然后會到第二步刘绣，再決定插入的策略。
- 過期計算:如果qmax隊頭的下標(biāo)等于i-w挣输，說明過期纬凤，直接彈出。
- 計算res值歧焦，當(dāng)i-w>=0的時候就可以記錄res的值了移斩。
qmax在其中的責(zé)任是負責(zé)維護窗口為w的子數(shù)組的最大值更新。
代碼
public static int[] getMaxWindow(int[] arr,int w){
if (arr == null || arr.length < w || w < 1){
return null;
}
LinkedList<Integer> qmax = new LinkedList<Integer>();//用來記錄最大值的更新
int[] res = new int[arr.length-w+1];//用來記錄結(jié)果
int index = 0;
for (int i = 0; i < arr.length; i++) {
//1到4步驟的過程
while (!qmax.isEmpty() && arr[qmax.peekLast()] <= arr[i]){
qmax.pollLast();
}
qmax.addLast(i);
//第5步:過期計算
if (qmax.peekFirst() == i-w){
qmax.pollFirst();
}
//第6步:記錄res值
if (i-w >= -1){
res[index++]=arr[qmax.peekFirst()];
}
}
return res;
}
public static void main(String[] args) {
int[] arr = new int[]{4,3,5,4,3,3,6,7};
int[] res = getMaxWindow(arr,3);
for(int r : res){
System.out.println(r);
}
}
