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

import java.util.*;
public class Solution {
    public ArrayList<Integer> maxInWindows(int[] num, int size) {
        ArrayList<Integer> res = new ArrayList<>();
        LinkedList<Integer> queue = new LinkedList<>();//单调队列
        for (int i = 0; i < num.length; i++) {
            //保证队列的单调性，队头元素总是当前窗口的最大值 的下标
            //如果队列尾元素小于当前元素则循环删除，保证队列的单调性
            while (!queue.isEmpty() && num[queue.peekLast()] < num[i]) {
                queue.pollLast();
            }
            //将当前元素加入队列
            queue.addLast(i);
            //先判断队头元素是否过期：即是否是当前窗口的值
            while (i - queue.peekFirst() + 1 > size) {
                queue.pollFirst();
            }
            //先判断当前窗口是否已满，再取当前窗口的最大值
            if (i >= size-1) {
                res.add(num[queue.peekFirst()]);
            }
        }
        return res;
    }
}