一、方法思路

1.暴力解法

找出所有滑动窗口中的最大值最直接的方法就是划分出每个窗口，并遍历其中元素找出最大值。

假设数组长度为n，窗口大小为k，该方法的时间复杂度为：O(nk)。

解题的效率不高。

2.双端队列优化

将双端队列保存当前或之后窗口最大元素的索引，保证队列头部始终是当前窗口的最大值。

思路如下：

1. 初始化一个双端队列dp和一个结果列表list
2. 遍历数组中元素，索引为i
1. 判断队首元素是否不在当前窗口范围（dq.peekFirst <= i - size）,如果是，弹出队首。
2. 将当前元素num[i]与队尾元素dq.peekLast比较，如果当前元素更大，将dq.peekLast弹出队尾，直到队列为空或者当前队尾元素更大。即能保持队列中的元素是递减的。
3. 将当前元素索引i加入队列
4. 判定窗口形成：当i >= size - 1时（0，1，2 --> 第一个窗口形成），将队首对应的元素加入结果列表。
3. 返回结果列表

二、代码实现

java代码实现双端队列优化滑动窗口，如下：

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param num int整型一维数组 
     * @param size int整型 
     * @return int整型ArrayList
     */
    public ArrayList<Integer> maxInWindows (int[] num, int size) {
        ArrayList<Integer> list = new ArrayList<Integer>();
        //双端队列
        if(num == null || size <=0 || size > num.length){
            return list;
        }

        Deque<Integer> dq = new LinkedList<Integer>();

        for(int i=0;i< num.length;i++){
            //移除超出窗口左侧的队首元素
            while(!dq.isEmpty() && dq.peekFirst() < i - size +1){
                dq.pollFirst();
            }
            //维护队列递减，移除比当前元素小的队尾元素
            while(!dq.isEmpty() && num[dq.peekLast()]<num[i]){
                dq.pollLast();
            }

            //正常入队
            dq.offerLast(i);
            //当队列中元素为3时形成窗口，并记录当前窗口的最大值
            if(i >= size -1){
                list.add(num[dq.peekFirst()]);
            }
        }

        return list;
    }
}