题目

给定一个数组和滑动窗口的大小，找出所有滑动窗口里数值的最大值。例如，如果输入数组{2,3,4,2,6,2,5,1}及滑动窗口的大小3，那么一共存在6个滑动窗口，他们的最大值分别为{4,4,6,6,6,5}； 针对数组{2,3,4,2,6,2,5,1}的滑动窗口有以下6个：

• {[2,3,4],2,6,2,5,1}
• {2,[3,4,2],6,2,5,1}
• {2,3,[4,2,6],2,5,1}
• {2,3,4,[2,6,2],5,1}
• {2,3,4,2,[6,2,5],1}

• {2,3,4,2,6,[2,5,1]}

  分析思路：

  双端队列：既可以从头部进出也可以从尾部进出。
  使用双端队列头部存储最大值的下标，使用尾部存储候选最大值的下标。
  在存入下标前，首先判断该下标对应的值是否大于队列尾部的候选值，如果大于就删除尾部，即将该值变为了候选最大值。
  如果队列头部的数字已经滑出了窗口，则滑出数字也需从队列头部删除掉。
  时间复杂度：O(N)
  空间复杂度：O(N)

  代码：

  ```java import java.util.*; public class Solution { public ArrayList maxInWindows(int [] num, int size){

    ArrayList<Integer> list = new ArrayList<Integer>();
    Deque<Integer> deque = new LinkedList<Integer>();
    //判断异常输入情况
    if(num==null||size<=0||size>num.length) return list;
    //开始滑动窗口
    for(int i=0;i<num.length;i++){
        //如果当前遍历到的数大于双端队列的末尾值（候选窗口最大值），
        //就去除掉队列的末尾值。
        while(!deque.isEmpty()&&num[i]>=num[deque.peekLast()]){
            deque.removeLast();
        }
        //若当前滑动窗口已滑出，则去掉队列首端的最大值
        if(!deque.isEmpty()&&i-deque.peekFirst()>=size){
            deque.removeFirst();
        }
        deque.addLast(i);
        //滑动索引大于size开始，每滑动一次就添加一次当前窗口极大值
        if(i>=size-1){
            list.add(num[deque.peekFirst()]);
        }
    }
    return list;

  } }

```