单调队列

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;
        
    }
}