滑动窗口算法问题及其衍生问题

文章目录

1. 滑动窗口相关题目
2. 这类问题在实际问题的应用场景
3. 如何求解这类问题

滑动窗口相关题目

这类问题在实际问题的应用场景

首先声明，我并不赞同为了刷题而刷题的行为。但是这一大批题目中的确有比较好的，特别是有些题目其实是现实实际问题的抽象，我认为将同一类的问题组合起来，由浅入深，逐步推进，进而寻找到解决一类问题的方法和思路，这样的题目还是刷得有价值的。
废话少说，首先说下滑动窗口在实际问题有哪些应用。
首先，最直接的应用就是网络协议中的TCP协议中传输数据的 TCP滑动窗口流控技术。
其次，既然在TCP流控会用到这样的技术，那么在应用层的流量控制其实也可以用到这样的技术（比如，令牌桶算法）

如何求解这类问题

对于静态的数据（数据和数据长度固定），常见的问题会是，对于一个滑动窗口（长度为k）求滑动窗口的最大、中位数、最小值的数组（对应题目 Sliding Window Maximum 、Sliding Window Median ）
对应的，对于动态的数据，常见的问题会是：在数据流中，对于一个滑动窗口（长度为k）求滑动窗口的最大数和中位数数组。

对于最大值问题，常见的解题套路

维护一个大顶堆，元素依次进入顶堆；
同时如果为了维护滑动窗口为k（如果有这样的条件和要求），对应的会有数组元素移除出顶堆（在这样的操作下，窗口就滑动起来了）；
只需要在对应的节点返回大顶堆的堆顶元素并添加到结果集中即可。

以问题 Sliding Window Maximum 为例实现上面的算法：

1
2
3

public int[] maxSlidingWindow(int[] nums, int k) {

}

题目中需要沟通的部分

首先对于题目中定义的函数需要处理对应参数的边界条件检查，如果是在面试环节，这些边界条件需要和面试官进行沟通，这里我们按照通常的处理手段来处理这些边界条件：

输入数组为null
输入数组为empty({})
k < 0
k > length

public int[] maxSlidingWindow(int[] nums, int k) {
  if (nums == null || nums.length) return nums;
  if (k < 0 || k > nums.length) return null;

  return null;
}

可能的解法以及对应复杂度分析

其次对于上面的算法，对于时间复杂度，输入的数组元素会被遍历有且仅有一次，遍历的过程里会有向大小为k的heap中插入和删除操作，根据时间复杂度的乘法法则，时间复杂度为 $O(nlog^k)$ , 空间复杂度上，由于使用了额外的heap空间所以空间复杂度为 $O(k)$, 以上是我们使用优先队列实现的复杂度分析;
对于这个问题其实还有其他的算法解决方案（如维护一个双端队列 dequeue，依次让数组元素入队出队，从而返回符合条件的结果， dequeue 入队和出队的时间复杂度都为 $O(1)$ 整体来看这样的算法时间复杂度为 $O(n)$ 空间复杂度为 $O(k)$ ），限于主题的原因，这里就不实现这个算法了。

代码实现

public int[] maxSlidingWindow(int[] nums, int k) {
  if (nums == null || nums.length) return nums;
  if (k < 0 || k > nums.length) return null;

  int length = nums.length;
  int[] result = new int[length - k + 1];
  PriorityQueue<Integer> maxHeap = new PriorityQueue(k, Collections.<Integer>reverseOrder());
  for (int i = 0; i < k; i++) {
    maxHeap.offer(nums[i]);
  }
  result[0] = maxHeap.peek();
  for (int j = k; j < length; j++) {
      maxHeap.offer(nums[j]);
      maxHeap.remove(nums[j - k]);
      result[j - k + 1] = maxHeap.peek();
  }

  return result;
}

测试用例

再次，关于测试用例，可以按照happyCase和badCase分为两大类：

HappyCase

nums = {1,3,-1,-3,5,3,6,7} , k = 3
nums = {1,3,-1,-3,5,3,6,7} , k = 1
nums = {1,3,-1,-3,5,3,6,7} , k = 8
nums = {1}, k = 1

BadCase

nums = null, k = 0;
nums = {}, k = 0;
nums = null, k = -1;
nums = {}, k = -1;
nums = {1, 2, 3}, k = 4;

对于这个问题我已经在我的Github工程中实现，并通过了单元测试工程测试：
算法实现：maxSlidingWindowHeap

对应单元测试： maxSlidingWindow …

对于中位数问题，常见的解题套路

维护两个堆：一个大顶堆，一个小顶堆；
这两个堆分别存储的是：

一个数组最小值到中位值（可能值）一段子数组
有序数组后半部分的子数组

那么如果滑动窗口长度是奇数，那么返回大顶堆的堆顶元素、如果滑动窗口长度是偶数，那么返回大顶堆和小顶堆的平均值即可；

这里实现过程中还需要注意的是为了维护滑动窗口固定长度的限制（如果有这样的条件和要求），需要控制元素的入堆和元素出堆的操作。

以问题 Sliding Window Median 为例实现以上算法：

1
2
3

public double[] medianSlidingWindow(int[] nums, int k) {

}

题目本身需要沟通的部分

这部分和max的问题类似，省略。

可能解及对应的复杂度分析

正如上面的算法描述，该算法会对数组中的元素进行有且仅有一次的遍历，过程中会涉及到至少一次入堆和一次出堆操作，以及常数次的堆平衡操作，因此根据乘法法则有该算法的时间复杂度为 $O(nlogk)$ , 空间复杂度为 $O(k)$ 虽然使用了两个堆，但是两个堆的大小之和为$k$。

代码实现及优化

public double[] medianSlidingWindow(int[] nums, int k) {
  if (nums == null || nums.length == 0) return nums;
  if (k < 0 || k > nums.length) return null;

  int length = nums.length;
  int[] result = new int[length - k + 1];
  PriorityQueue<Integer> minHeap = new PriorityQueue();
  PriorityQueue<Integer> maxHeap = new PriorityQueue(100, Collections.reverseOrder());
  
  for (int i = 0; i < length; i++) {
      // enHeap
      if (maxHeap.size() == 0 || nums[i] <= maxHeap.peek()) {
          maxHeap.offer(nums[i]);
      } else {
          minHeap.offer(nums[i]);
      }
      // rebalance
      rebalance(maxHeap, minHeap);
      // remove element from heap
      if (i >= k) {
          if (nums[i - k] <= maxHeap.peek()) {
              maxHeap.remove(nums[i - k]);
          } else {
              minHeap.remove(nums[i - k]);
          }
      }
      // rebalance
      rebalance(maxHeap, minHeap);
      // output median
      if (i >= k - 1) {
          result[i - k + 1] = (k % 2 == 0)
          ? (maxHeap.peek() + minHeap.peek()) / 2.0
          : maxheap.peek();
      }
  }

  return result;
}

private void rebalance(PriorityQueue<Integer> maxHeap, PriorityQueue<Integer> minHeap) {
    while (maxHeap.size() < minHeap.size()) maxHeap.offer(minHeap.pop());
    while (minHeap.size() < maxHeap.size() - 1) minHeap.offer(maxHeap.pop());
}

看似好像这个问题就这样解决了，但其实这样的实现还是有问题的，在计算中位数的这部分代码中，暗藏一个边界条件，对于加法操作如果两个整数都比较大的情况，两个数的和可能会出现整数溢出，因此，这里需要特殊的技术处理，这里先买个关子，请仔细思考后进行实现。

参考实现： medianSlidingWindow

测试用例的部分

这里测试用例与max相似，唯一不同的是对整数溢出情况的考虑：

nums = {2147483647}; k = 2

测试工程参考实现： medianSlidingWindow

引申问题

既然可以使用大小顶堆实现中位数的算法，如果改造下堆的平衡函数实现其实可以实现 90、99 分位数的滑动窗口。