題目
有一個整形數(shù)組arr和一個大小為w的窗口從數(shù)組的最左邊滑到最右邊烘贴，窗口每次向右邊滑一個位置撮胧。
??例如：數(shù)組為[4,3,5,4,3,3,6,7]，窗口大小為3時：
[4,3,5],4,3,3,6,7 5
4,[3,5,4],3,3,6,7 5
4,3,[5,4,3],3,6,7 5
4,3,5,[4,3,3],6,7 4
4,3,5,4,[3,3,6],7 6
4,3,5,4,3,[3,6,7] 7
實現(xiàn)思路
使用淘汰劣勢元素的方式進行實現(xiàn)锻离，每個元素有位置和值兩個屬性墓怀，使用隊列進行存儲，處理原則：
- 新加入的元素捺疼，使用值較大的優(yōu)勢，可以淘汰已存儲在隊列中比他小的元素卧秘。
- 新加入的元素官扣，無法淘汰隊列中比其大的元素，但新加入的元素有位置優(yōu)勢惕蹄，那么就需要排在大元素之后。
- 每次移動窗口卖陵，隊頭不在窗口范圍內(nèi)，需要淘汰棒旗。
使用上面的思路進行實現(xiàn)撩荣，那么每次移動窗口，隊頭的元素就是對大的值了餐曹。
實現(xiàn)代碼
package com.github.zhanyongzhi.interview.algorithm.stacklist;
import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;
import java.util.List;
/**
* 獲取各個窗口的最大值
*/
public class GetWindowMax {
public List<Integer> getWindowMax(Integer[] input, int windowSize) {
Deque<Integer> maxIndexQueue = new LinkedList<Integer>();
List<Integer> result = new ArrayList<>();
for (int i = 0; i < input.length; i++) {
if(maxIndexQueue.isEmpty()) {
maxIndexQueue.push(i);
continue;
}
//移除過期的索引
if(maxIndexQueue.peekFirst() + 3 <= i)
maxIndexQueue.removeFirst();
//當(dāng)前如果是最大的數(shù),則刪除前面比其小的數(shù)字的索引,否則直接加到最后
Integer lastElement = input[maxIndexQueue.peekLast()];
Integer curElement = input[i];
while(curElement >= lastElement){
maxIndexQueue.removeLast();
if(maxIndexQueue.isEmpty())
break;
lastElement = input[maxIndexQueue.peekLast()];
}
maxIndexQueue.addLast(i);
//索引未夠window size,不需要獲取最大值
if(i < (windowSize - 1))
continue;
//最大值為開頭的數(shù)字
result.add(input[maxIndexQueue.peekFirst()]);
}
return result;
}
}
