数据流中的移动平均值
难度:
标签:
题目描述
代码结果
运行时间: 41 ms, 内存: 19.2 MB
/*
* 思路:
* 使用Java Stream API,我们可以通过流操作简化代码。需要注意的是,Java Stream API通常用于一次性操作,
* 而不是持续的数据流。因此,仍然需要使用队列来存储最近的n个值。
*/
import java.util.LinkedList;
import java.util.Queue;
import java.util.stream.Collectors;
public class MovingAverageStream {
private final Queue<Integer> queue;
private final int maxSize;
private double sum;
public MovingAverageStream(int size) {
this.queue = new LinkedList<>();
this.maxSize = size;
this.sum = 0;
}
public double next(int val) {
if (queue.size() == maxSize) {
sum -= queue.poll();
}
queue.offer(val);
sum += val;
return queue.stream().mapToDouble(num -> num).average().orElse(0.0);
}
public static void main(String[] args) {
MovingAverageStream m = new MovingAverageStream(3);
System.out.println(m.next(1)); // 1.0
System.out.println(m.next(10)); // 5.5
System.out.println(m.next(3)); // 4.66667
System.out.println(m.next(5)); // 6.0
}
}
解释
方法:
该题解使用了双端队列 deque 来实现移动平均值的计算。在初始化时,记录了窗口大小 size,并初始化了一个双端队列 queue 和滑动窗口内的元素和 sum_v。在每次调用 next 方法时,将新的元素 val 加入队列,并更新窗口内元素和 sum_v。如果队列长度超过了窗口大小 size,就将队首元素弹出,并相应地减少 sum_v。最后返回 sum_v 除以队列长度,即为当前的移动平均值。
时间复杂度:
O(1)
空间复杂度:
O(size)
代码细节讲解
🦆
在初始化MovingAverage类时,将size、queue和sum_v作为属性进行初始化的原因是什么?
▷🦆
为什么选择双端队列deque而不是其他数据结构如列表或链表来实现这个滑动窗口?
▷🦆
next方法中,当队列长度超过窗口大小时,只是简单地减去队首元素。请问这种处理方式是否会在某些极端情况下导致sum_v的计算不准确?
▷🦆
在计算移动平均值时,直接使用sum_v除以当前队列长度,这种做法在窗口未满时是否合适?
▷