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

2017-10-29 23:40:30

题目描述：

有一个整型数组arr和一个大小为w的窗口从数组的最左边滑到最右边，窗口每次向右边滑一个位置。窗口中每次会产生一个最大值，求这n-w+1最大值组成的数组。

要求时间复杂度为O（n）。

求解：

举例：[4,3,5,4,3,3,6,7]，窗口大小为3

结果：[5,5,5,4,6,7]

采用一个双端队列来维护窗口中的最大值，以及可能成为最大值的数。

定义一个双端队列qmax用来保存最大值的下标。

当遍历到arr[i]的时候，

~ 进队列的策略：

1、如果qmax为空，则直接将下标放入队列

2、如果qmax非空，则比较arr[i]和队列中的队尾j对应的arr[j]的大小。

　　　　　　　　   若arr[j]>arr[i]，那么表示arr[i]有可能在接下来成为最大值，所以将i放入队列

　　　　　　　　   若arr[j]<=arr[i]，那么表示a[j]已经不可能是最大的值了，所以将arr[j]抛出，继续进行比较。

~ 出队列的策略：

如果此时队首的下标k满足i-k=w，则表示当前的队首元素已经过期，所以可以将队首的元素抛出。

public class MaxWindow {    public int[] getMaxWindow(int[] arr,int w)    {        LinkedList
    
      qmax = new LinkedList<>();        int[] rst=new int[arr.length-w+1];        int j=0;        for(int i=0;i
     
      =w-1) rst[j++]=arr[qmax.getFirst()];        }        return rst;    }}
     
    

转载地址：https://www.cnblogs.com/hyserendipity/p/7751986.html 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！