class Solution {
public int[] maxInWindows(int[] nums, int k) {
int[] arr=null;
if(nums==null){
return arr;
}
if(nums.length==0){
return arr;
}
if(k>nums.length){
return arr;
}

  //定义一个队列保存可能最大值的下标

  int[] max=  new int[nums.length-k+1];//最多有nums.length-k+1 个
    LinkedList<Integer>  list = new  LinkedList<Integer>();
  int count =0;
 // 还没到窗口

 for(int i=0;i<k;i++){
     // 如果队列不为空并且队尾的元素小于当前则删除
    while( list.size()>0 &&nums[i] >nums[list.peekLast()] ){
         list.removeLast();    
    }
    list.addLast(i);


 }

 // 已经遍历到窗口大小开始滑动窗口
  for(int i=k; i<nums.length;i++){

    //记录最大值

    max[count++] =nums[list.getFirst()];//
     // 如果队列不为空并且队尾的元素小于当前则删除
    while( list.size()>0 &&nums[i] >nums[list.peekLast()] ){
         list.removeLast();    
    }
    //对队头最大值超出窗口 移除

    if((list.size()>0 )&&((i-list.getFirst())>=k)){

     list.removeFirst();

    }
    //当前元素添加到队尾
    list.addLast(i);
 //  System.out.println(list);
  }
  //System.out.println(list);
  if(list.size()>0)
  max[count++]=nums[list.getFirst()];//最后一个最大值


   return max;

}

}