生成窗口最大值数组

题目

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

例如,数组为【4,3,5,4,3,3,6,7】,窗口大小为3时:

窗口数组   最大值

[4 3 5] 4 3 3 6 7 5

4 [3 5 4] 3 3 6 7 5

4 3 [5 4 3] 3 6 7 5

4 3 5 [4 3 3] 6 7 4

4 3 5 4 [3 3 6] 7 6

4 3 5 4 3 [3 6 7] 7

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

请功能实现一个函数,

输入:整型数组arr,窗口大小为w;

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

以本题为例,结果应该返回【5,5,5,4,6,7】

分析

本题的关键是利用双端队列来实现窗口最大值的更新,窗口中的最大值可以覆盖掉该最大值之前的数字信息,利用这一特性来设计双端队列。

设双端队列为qmax,假设遍历到arr[i]:

qmax的放入规则为:

1、若qmax为空,则直接将i放入qmax

2、若qmax不为空,则比较arr[i]与arr[qmax.peekLast()],

若arr[i]<arr[qmax.peekLast()],则直接将i放入qmax;

若arr[i]>=arr[qmax.peekLast()],则将qmax对尾弹出,重新执行第2步。

qmax的弹出规则为:

若qmax队头的下标等于i-w,则说明当前qmax队头的下标已过期,弹出当前队头。

该算法的时间复杂度为O(n)

public class GetMaxWindow {
      public int[] getMaxWindow(int[] arr, int w) {
          if(arr == null || arr.length == 0) {
              return null;
          }
          int i = 0;
          int index = 0;
          int[] res = new int[arr.length - w + 1];
          LinkedList<Integer> max = new LinkedList<>();
          while (i < arr.length) {
              while (!max.isEmpty() && arr[i] >= arr[max.peekLast()]) {
                  max.pollLast();
              }
              max.offerLast(i);
              if (max.peekFirst() == i - w) {
                  max.pollFirst();
              }
              //确保窗口已经形成
              if (i >= w - 1) {
                  res[index++] = arr[max.peekFirst()];
              }
              i++;
          }
          return res;
      }
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容

  • 姓名:李淑瑛 224期学员 289期志工 325期志工 423期志工 公司:绍兴翔鹰纺织品有限公司 部门:人事行政...
    李淑瑛阅读 128评论 0 0
  • 第一章 引言 shell 是和键盘打交道的,但你也可以在终端仿真器里使用鼠标。X 窗口系统 (使 GUI 工作的底...
    cccshuang阅读 355评论 0 0
  • 原文链接:www.zcool.com.cn/article/ZNDA1ODcy.html 首先明确表示在ios 中...
    走近科学探索发现阅读 3,389评论 5 1
  • 感恩春节孩子回老家过年,总体来说是开心的,感谢你们这每个人还是一如既往对我好!感谢我的前夫,其实我看见你在改变,并...
    周红zh阅读 193评论 0 0
  • 姓名 徐海燕 公司 宁波四维尔工业有限责任公司 【日精进打卡第310天】 【知~学习】 《六项精进》大纲今日5遍 ...
    柠檬茶_4592阅读 206评论 0 0