题解 | #滑动窗口的最大值#

单调队列——java版
https://liyanzu0926.github.io/2022/03/13/page-4/

public class Solution {
    public ArrayList<Integer> maxInWindows(int [] num, int size) {
        Deque<Integer> queue = new LinkedList<>();
        ArrayList<Integer> res = new ArrayList<>();
        // 初始窗口
        for(int i = 0; i < size; i++){
            while(!queue.isEmpty() && num[i] > num[queue.getLast()]){
                queue.pollLast();
            }
            queue.offer(i);
        }
        res.add(num[queue.getFirst()]);
        for(int i = size; i < num.length; i++){
            // 维护单调队列
            while(!queue.isEmpty() && num[i] > num[queue.getLast()]){
                queue.pollLast();
            }
            queue.offer(i);
            // 将下标不在窗口中的元素移出窗口
            while(!queue.isEmpty() && queue.getFirst() < i - size + 1){
                queue.pollFirst();
            }
            res.add(num[queue.getFirst()]);
        }
        return res;
    }
}