有一个整型数组arr 和一个 大小为w的窗口从数组的最左边滑倒最右边，窗口每次向右边滑动一个位置

如果数组长度为n， 窗口大小为w， 则一共产生 n-w+1 个窗口的最大值

 

请实现一个函数：

 输入  整型数组 arr， 窗口大小 w

 输出 一个长度为 n-w+1 的数组res  res[i] 表示每一种窗口状态下的最大值。

 

 

本题的关键在于利用双端队列来实现最大值的更新。首先生成双端队列qmax， qmax中存放数组arr的下标

 

看代码：

package TT;import java.util.LinkedList;public class Test125 {	public int[] getMaxWindow(int[] arr, int w){		 		if(arr==null || w <1 || arr.length 
     
       qmax = new LinkedList
      
       ();		int[] res = new int[arr.length-w+1];		int index=0;		for(int i =0; i
       
        =w-1){				res[index++]=arr[qmax.peekFirst()];			}		}		return res;	}			}