算法学习——剑指 Offer II 041. 滑动窗口的平均值(Java实现)

1. 题目

这是LeetCode上的 [041，滑动窗口的平均值]，难度为 [简单]

2. 题解

2.1 思路分析

根据题意，模拟滑动窗口的过程，如下

假设滑动窗口的大小为3，当第1次调用next函数时在滑动窗口中添加整数1，此时窗口中只有一个数字1，因此返回平均值为1。如下所示

当第2次调用next函数时添加整数2，此时窗口中有两个数字1，2，因此返回平均值为1.5，如下所示

当第3次调用next函数时添加整数3，此时窗口中有三个数字1，2，3，因此返回平均值2，如下所示

第4次次调用next函数时添加数字4，由于受到窗口大小的限制，滑动窗口中最多只能有3个数字，因此第1个数字1将滑出窗口，此时窗口中包含3个数字2，3，4，返回平均值3，如下所示

总结： 每次调用next函数时，可以向滑动窗口添加一个值，并算出滑动窗口的所有值的平均值，若在滑动窗口的已满的情况下添加一个值，需要把滑动窗口最先添加的值删除掉，因此满足先出先出的特点，可以使用队列模拟滑动窗口

平均值的计算

方式1： 一种直观的方法是每次调用next函数时都累加窗口中的所有值之和，然后除于窗口的大小。如果窗口的大小为n，那么每次计算的平均值的时间复杂度为O(n)

方式2： 如果每次调用next函数添加值时，都把添加的值累加到一个数中(用sum表示)，即sum + val。若在滑动窗口的已满的情况下添加一个值，还需要把sum的值减去最先添加的值，因此最多只需一次加法和减法就可以算出所有数之和，故时间复杂度为O(1)

2.2 代码实现

class MovingAverage {
    private Queue<Integer> nums;
    private int capacity;
    private double sum;
    public MovingAverage(int size) {
        // 创建一个队列模拟滑动窗口
        nums = new LinkedList<>();
        // 初始滑动窗口的大小
        capacity = size;
    }

    public double next(int val) {
        // 在滑动窗口中添加一个值
        // 把添加的值累加到sum中
        nums.offer(val);
        sum += val;
       /* 若队列的大小超过滑动窗口的大小，需要删除滑动窗口最先添加的值
       * 并把删除的值从sum中减去*/
        if (nums.size() > capacity) {
            sum -= nums.poll();
        }
        return sum / nums.size();
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24