题解 | #滑动窗口的最大值#
滑动窗口的最大值
http://www.nowcoder.com/practice/1624bc35a45c42c0bc17d17fa0cba788
单调队列
import java.util.*;
public class Solution {
public ArrayList<Integer> maxInWindows(int [] num, int size) {
//使用一个大小为size的双端队列保存最大值,维持队首元素为最大值,当窗口滑动的时候,删除小于等于当前划出窗口的元素
ArrayDeque<Integer> max = new ArrayDeque<>();
ArrayList<Integer> res = new ArrayList<>();
int len = num.length;
if(len==0 || len < size || size < 1) return res;
for(int i = 0;i < len;i++){
while(!max.isEmpty() && num[max.peekLast()]<num[i]){
max.pollLast();
}
max.addLast(i);
//判断队列的头部元素是否过期
if(max.peekFirst()+size <= i){
max.pollFirst();
}
//判断是否形成了窗口
if(i+1>=size){
res.add(num[max.peekFirst()]);
}
}
return res;
}
}