算法题/3.md · MeenJ./java面试迷你版

生成窗口最大值数组

意思是这样的，有一个数组arr，在arrs上划动长度为3的窗口，每到一个新的位置上的时候，都会记录下三个数字总和，最后总和最大即为输出结果

[4, 3, 5, 4, 3, 3, 6, 7]

好像挺简单的，直接手撕代码：

public static void main(String[] args) {
  int[] arr = new int[]{4, 3, 5, 4, 3, 3, 6, 7};
  int max = arr[0] + arr[1] + arr[2];
  for (int i = 1; i < arr.length - 2; i++) {
    int temp = arr[i] + arr[i + 1] + arr[i + 2];
    if (temp > max) {
      max = temp;
    }
  }
  System.out.print(max);
}

没毛病的样子，但是多年的从业经验告诉我，暴力解决不了问题，这题肯定有炸！！没那么简单。

直到我重新看了一遍题目，发现我，看错了题目的意思。

题目本意是，还是上面的数组，但是每一次向右滑动一格，都记录下窗口的最大值，来个例子：

[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

那么输出的结果就是[5, 5, 5, 4, 6, 7]。

但是为时已晚，先睡一觉明天再想办法做它。

2020-07-07 23:07

今天偶尔想起来这个问题，觉得除了暴力破解之外，比较好的办法是避免掉里面重复的比较，例如下标0、1、2中计算了最大的值，1、2、3中其实1和2的比较已经计算过了，在代码实现上要注意这个，可以把时间从O(N + M^2)降为 O(N + M)。

第一次的版本自然是什么都没优化的样子：

  public static void main(String[] args) {
    int[] arr = new int[]{4, 3, 5, 4, 3, 3, 6, 7};
    //  结果数组的长度是输入数据长度减去窗口长度+1
    int[] resArr = new int[arr.length - 3 + 1];
    int j = 0;
    for (int i = 0; i < arr.length - 2; i++) {
      resArr[j] = Math.max(arr[i], Math.max(arr[i + 1], arr[i + 2]));
      j++;	
    }
    for (int i = 0; i < resArr.length; i++) {
      System.out.print(resArr[i] + " ");
    }
  }

优化目的还没达成，主要在于如何消化Math.max(arr[i], Math.max(arr[i + 1], arr[i + 2]));这段代码。

2020-07-09 00:14

其实上面的思路我写不出实现的代码，在看过书上一页多的解析之后，我上面就是在乱说。书上给出的做法是加多一个双向链表，即可实现O（N）复杂度。我也诚服了，赶紧学习观摩下。

思路：

创建一个双向队列qmax。

假设遍历到arr[i]， qmax的放入规则为：

如果qmax为空，直接把下标i放进qmax，放入过程结束。
如果qmax不为空，取出当前qmax队尾存放的下标，假设为j。

1）如果arr[j] > arr[i]，直接把下标i放进qmax的队尾，放入过程结束。

2）如果arr[j] <= arr[i]，把j从qmax中弹出，重复qmax的放入规则。

意思就是说，不断地把当前i下标的值和qmax队列尾部存放的下标对应的值对比，i下标值更大的话就不断的取出队尾，直到队列为空或者j下标的值更大。qmax成了维护窗口为w长度的子数组的最大值更新的结构。这个过程中收集下来的最大值就是题目的结果数组。

2020-07-12 12:35

其实回味一下上面说的话，我也感觉迷迷糊糊不好理解。建议按给出的输入用例在纸上比划比划。我直接看下实现代码。

  public static void main(String[] args) {
    int[] arr = new int[]{4, 3, 5, 4, 3, 3, 6, 7};
    int w = 3;  //  设置窗口长度
    //  结果数组的长度是输入数据长度减去窗口长度+1
    int[] resArr = new int[arr.length - w + 1];
    //  保存滑动窗口最大的值双向队列
    LinkedList<Integer> qmax = new LinkedList();
    int j = 0; //  记录结果队列下标
    for (int i = 0; i < arr.length; i++) {
      while (!qmax.isEmpty() && arr[qmax.peekLast()] <= arr[i]) {
        //  qmax队尾元素对应的数组的值不够arr[i]大的话
        qmax.removeLast();
      }
      //  再把arr[i]放到qmax
      qmax.addLast(i);
      //  维护qmax的长度不超过滑动窗口的长度，并且保存的下标都在此时滑动窗口内
      if (qmax.peekFirst() == (i - w)) {
        qmax.removeFirst();
      }
      //  从i = 2开始采用结果
      if (i >= (w - 1)) {
        resArr[j++] = arr[qmax.peekFirst()];
      }
    }
    //  输出结果
    for (int val : resArr) {
      System.out.print(val + " ");
    }
  }

以上过程中，arr的每个元素最多只会有一次进和出qmax，总体的时间复杂度为O(N)。果然厉害，不学习下都不行，如何充实提升自己，我建议加下这位小姐姐的微信了解下，拿一些学习资料。

*以上例题和正确的解析来自《程序员代码面试指南》。

题外话：

说到滑动窗口，我想起来了限流算法，就是下面gitee提到的滑动窗口。

https://gitee.com/linjiayu_index/javaLearn/blob/master/pages/%E9%99%90%E6%B5%81.md

计数器
滑动窗口
漏桶：规定固定容量的桶，对于流进的水我们无法估计，对于流出的水我们可以控制。
令牌桶：一个线程往令牌桶加token，满则不加，请求是取走一个，空了就拒绝请求。
spring cloud gateway
sentinel：结合spring-cloud-alibaba。

滑动窗口和上面题目提到的意思差不多，是为了解决计数器不能很好地处理的时间边缘问题，例如计数器是让1分钟进100个请求，但是请求都集中在第1分钟里的第50-60秒，这一步没问题，但是第2分钟的第0-10秒又进来了100个请求，那么短短的20秒内，进来了200个请求，无疑和是突破了1分钟只能进100个请求的限制。所以这个时候采用滑动窗口，例如现在是从第一分钟的第0秒开始，每次滑动60秒区间，在滑动区间内计算请求量，超过了100则发出限制。

MeenJ. / java面试迷你版

题外话：

简介

发行版

贡献者

近期动态

MeenJ. / java面试迷你版 .gitee-modal { width: 500px !important; }

题外话：

简介

发行版

贡献者

近期动态

搜索帮助

MeenJ. / java面试迷你版