java 单调队列

import java.util.*;
public class Solution {
    public ArrayList<Integer> maxInWindows(int [] num, int size){
        ArrayList<Integer> res = new ArrayList<>();
        if(size > num.length || size == 0){
            return res;
        }
        // 单调队列
        int j = 0;
        Deque<Integer>  queue = new ArrayDeque<>();
        // 初始化第一个窗口
        while(j < size){
            while(!queue.isEmpty() && num[j] > queue.peekLast()){
                queue.pollLast();
            }
            queue.addLast(num[j]);
            j++;
        }
        res.add(queue.peekFirst());
        // 以窗口右端index遍历一次
        while(j < num.length){
            // 如果上次窗口左端等于单调队列中最大的，要移除掉
            if(num[j-size] == queue.peekFirst()){
                queue.pollFirst();
            }
            // 新进来的值要更新队列维持其单调递减性
            while(!queue.isEmpty() && num[j] > queue.peekLast()){
                queue.pollLast();
            }
            // 将新值作为新窗口右端
            queue.addLast(num[j]);
            j++;
            // 添加每个窗口的最大值(单调队列的第一个元素)
            res.add(queue.peekFirst());
        }
        return res;
    }
}