文章目录
  1. 1. 滑动窗口相关题目
  2. 2. 这类问题在实际问题的应用场景
  3. 3. 如何求解这类问题
    1. 3.1. 对于最大值问题,常见的解题套路
      1. 3.1.1. 题目中需要沟通的部分
      2. 3.1.2. 可能的解法以及对应复杂度分析
      3. 3.1.3. 代码实现
      4. 3.1.4. 测试用例
        1. 3.1.4.1. HappyCase
        2. 3.1.4.2. BadCase
    2. 3.2. 对于中位数问题, 常见的解题套路
      1. 3.2.1. 题目本身需要沟通的部分
      2. 3.2.2. 可能解及对应的复杂度分析
      3. 3.2.3. 代码实现及优化
      4. 3.2.4. 测试用例的部分
    3. 3.3. 引申问题

滑动窗口相关题目

  1. Kth Largest Element in an Array
  2. Sliding Window Maximum
  3. Kth Largest Element in a Stream
  4. Sliding Window Median
  5. Find Median from Data Stream

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

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

如何求解这类问题

  • 对于静态的数据(数据和数据长度固定),常见的问题会是,对于一个滑动窗口(长度为k)求滑动窗口的最大、中位数、最小值的数组(对应题目 Sliding Window MaximumSliding Window Median

  • 对应的,对于动态的数据,常见的问题会是:在数据流中,对于一个滑动窗口(长度为k)求滑动窗口的最大数和中位数数组。

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

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

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

1
2
3
public int[] maxSlidingWindow(int[] nums, int k) {

}

题目中需要沟通的部分

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

  • 输入数组为null
  • 输入数组为empty({})
  • k < 0
  • k > length
1
2
3
4
5
6
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)$ ),限于主题的原因,这里就不实现这个算法了。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
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 …

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

维护两个堆: 一个大顶堆,一个小顶堆;
这两个堆分别存储的是:

  1. 一个数组最小值到中位值(可能值)一段子数组
  2. 有序数组后半部分的子数组

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

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

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

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

}

题目本身需要沟通的部分

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

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

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

代码实现及优化

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
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 分位数的滑动窗口。

文章目录
  1. 1. 滑动窗口相关题目
  2. 2. 这类问题在实际问题的应用场景
  3. 3. 如何求解这类问题
    1. 3.1. 对于最大值问题,常见的解题套路
      1. 3.1.1. 题目中需要沟通的部分
      2. 3.1.2. 可能的解法以及对应复杂度分析
      3. 3.1.3. 代码实现
      4. 3.1.4. 测试用例
        1. 3.1.4.1. HappyCase
        2. 3.1.4.2. BadCase
    2. 3.2. 对于中位数问题, 常见的解题套路
      1. 3.2.1. 题目本身需要沟通的部分
      2. 3.2.2. 可能解及对应的复杂度分析
      3. 3.2.3. 代码实现及优化
      4. 3.2.4. 测试用例的部分
    3. 3.3. 引申问题