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

/**
*	主要是运用的Deque双向队列 ， 双向队列中的元素降序排列 。每次添加进入的元素都要进行判断，如果大于队尾的元
*素，就删除队尾的元素 ，直到找到一个大于该元素的元素 或者队列为空时 将该元素添加至队尾，用begin记录头元素的
*   下标 ，当头元素下标 + size < i 时 队头元素失效 ，pop出对头元素。当 i+1>= 5时窗口形成，每次都将对头元素加入 集合中 。
*/




import java.util.*;
public class Solution {



    public ArrayList<Integer> maxInWindows(int [] num, int size) {
        if(num.length < size || size < 1 || num.length == 0 ) return new ArrayList<Integer>();

         ArrayList<Integer> list =  new ArrayList<>();
         //主要是保证deque中的元素是降序排列
        ArrayDeque<Integer> deque = new ArrayDeque<>();

        int begin = -1;

        for(int i = 0 ; i < num.length ; i++){
            while(!deque.isEmpty() && deque.getLast() < num[i]){
                //将deque中小于当前元素的值舍弃 
                deque.pollLast();
            }
                //将当前元素加入deque中
            deque.add(num[i]);
            if(deque.size() == 1) begin = i;  //记录新的头部的位置
            
            //判断deque头部元素是否过期
            if(begin + size <= i){
                deque.pollFirst();
            }
            
            //判断窗口是否形成 形成则返回队首元素 
            if(i+1 >= size)
            {
                list.add(deque.peekFirst());
            }

        }



       

        return list;
    }


}