剑指64.滑动窗口的最大值

import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;
public class Solution {
    public ArrayList<Integer> maxInWindows(int [] num, int size) {
        ArrayList<Integer> list = new ArrayList<>();
        if (num == null || size < 1 || num.length < size)
            return list;
        // 双端队列,deque里存的是数组的index，不是数组的值
        Deque<Integer> deque = new LinkedList<>();
        for (int i = 0; i < num.length; i++) {
            //Step1: 头: 移除头部, 保证窗口的长度范围
            if (!deque.isEmpty() && (i - deque.getFirst()) >= size){ //这个条件也可以换成 deque.getFirst() < (i - (size - 1))
                deque.removeFirst();
            }
            //Step2: 尾: 移除尾部小于当前值的元素, 去除不可能的元素
            while (!deque.isEmpty() && num[i] >= num[deque.getLast()]){
                deque.removeLast();
            }
            //Step3: 尾部加入, 滑动窗口向右扩充
            deque.addLast(i);
            //Step4: 头, 从头部返回极大值
            if (i >= size - 1){
                list.add(num[deque.getFirst()]);
                //list.add(num[deque.peekFirst()]); //所有的dq.getFirst()也可以换为dq.peekFirst()
            }
        }
        return list;
    }
}