本文共 696 字，大约阅读时间需要 2 分钟。

【题目】

给出一个整形数组，例如arr = {5,4,3,5,6,7,6}，窗口大小为w=3，窗口每次向右移动一位，输出每个窗口中最大值组成的数组。 [5,4,3,]5,6,7,6 窗口最大值为5 5,[4,3,5,]6,7,6 窗口最大值为5 5,4,[3,5,6,]7,6 窗口最大值为6 5,4,3,[5,6,7,]6 窗口最大值为7 5,4,3,5,[6,7,6] 窗口最大值为7 则输出的数组为{5,5,6,7,7};

【解答】

对于一个给定的数组，求得的最终数组长度可以确定是arr.length - w +1, 本题重点是使用双端队列来更新最大值小标，并同时将最大值存入数组中。保证时间复杂度为O(n)。

【代码】

//窗口最大值数组的方法    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;    }
     
    
   

转载地址：http://qnfen.baihongyu.com/