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

import java.util.*;
public class Solution {
    public ArrayList<Integer> maxInWindows(int [] nums, int size) {
        if(nums.length == 0 || size == 0) return new ArrayList();
        ArrayList<Integer> res = new ArrayList<>();
        Deque<Integer> deque = new LinkedList<>();
        for(int j=0, i=1-size; j<nums.length; i++, j++) {
            //删除deque中对应的nums[i-1]
            if(i>0 && deque.peekFirst() == nums[i-1])
                deque.removeFirst();    //如滑出元素是队列中最大元素进行处理，即队首元素出队，否则不处理
            //删除队列中所有小于nums[j]的元素 以保持deque递减
            while(!deque.isEmpty() && deque.peekLast()<nums[j])
                deque.removeLast();
            //nums[j]添加到队尾
            deque.addLast(nums[j]);

            //记录窗口最大值
            if(i>=0) res.add(deque.peekFirst());
        }
        return res;
    }
}