JZ59 滑动窗口的最大值

给定一个长度为 n 的数组 nums 和滑动窗口的大小 size ，找出所有滑动窗口里数值的最大值。

使用双端队列保存当前窗口中最大的值，操作步骤如下：

1. 如果队列中没有元素，则直接入队。

2. 如果新增的元素比队尾的元素小，直接入队。

3. 如果新增的元素比队尾的元素大，则从队尾开始依次弹出较小的元素，直到队列为空，或者队尾的元素比当前元素大

4. 当队头元素不在滑窗内部时，从队头弹出。

5. 在包含窗口大小个元素的位置开始，计算窗口的最大值。

import java.util.*;
public class Solution {
    public ArrayList maxInWindows(int [] num, int size) {
        if (num == null || num.length == 0 || size < 1 || size > num.length){
            return new ArrayList();
        }
        
        // 结果集
        ArrayList result = new ArrayList();
        // 双端队列
        LinkedList window = new LinkedList();
        
        // 依次遍历每个元素
        for (int i = 0; i < num.length; i++){
 
            // 队尾元素比当前元素小，依次弹出，直到队列为空或者队尾元素比当前元素大
            while (!window.isEmpty() && num[window.peekLast()] <= num[i]){
                window.pollLast();
            }
            
            // 队列被弹空了或者出现了比当前元素大的时候，将新元素放入队尾
            window.addLast(i);
            
            // 当前位置减去滑窗的大小就是窗口的起始位置，若恰好等于队头元素的位置，说明队头的元素过期了，出队
            if (i - size == window.peekFirst()){
                window.pollFirst();
            }
            
            // 从满足窗口大小的元素进入窗口处开始统计最大值
            if (i >= size - 1){
                result.add(num[window.peekFirst()]);
            }
        }
        
        return result;
    }
}