leetcode
leetcode 301 ~ 350
数据流中的移动平均值

数据流中的移动平均值

难度:

标签:

题目描述

代码结果

运行时间: 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作为属性进行初始化的原因是什么?
在`MovingAverage`类的初始化中,`size`用于设置滑动窗口的大小,这是计算移动平均值的核心参数。`queue`作为双端队列,用于存储滑动窗口中的元素,这使得元素的进入和退出都可以高效地进行。`sum_v`则用于存储当前队列中所有元素的和,这样在每次计算移动平均值时,可以避免重新遍历队列计算总和,提高效率。整体来看,这三个属性共同维护了滑动窗口的状态,是算法实现的基础。
🦆
为什么选择双端队列deque而不是其他数据结构如列表或链表来实现这个滑动窗口?
双端队列`deque`被选择是因为它支持两端的高效元素添加和删除操作(均为O(1)时间复杂度)。对比之下,列表(如Python中的list)在列表的起始位置插入或删除元素的时间复杂度是O(n),因为需要移动其他所有元素。虽然链表可以支持O(1)时间复杂度的元素添加和删除,但在Python中使用链表(如实现自定义链表或使用库)通常不如直接使用`deque`方便和高效。因此,`deque`是实现滑动窗口这种数据结构的理想选择。
🦆
next方法中,当队列长度超过窗口大小时,只是简单地减去队首元素。请问这种处理方式是否会在某些极端情况下导致sum_v的计算不准确?
在`next`方法中,当队列长度超过窗口大小时,简单地减去队首元素的处理方式是准确的,前提是没有发生数据类型溢出或精度问题。在常规使用中,只要确保`sum_v`的数据类型(如Python中的int)能够处理累加值的大小,这种实现就不会导致计算不准确。Python的int类型通常可以处理非常大的整数,因此在一般情况下不会有问题。
🦆
在计算移动平均值时,直接使用sum_v除以当前队列长度,这种做法在窗口未满时是否合适?
当窗口未满时,直接使用`sum_v`除以当前队列长度是合适的,因为这反映了窗口内实际存在的所有元素的平均值。这种处理方式确保了在任何时候计算得到的都是当前窗口内所有元素的真实平均值。因此,无论窗口是否已满,这种计算方法都是正确和适当的。

相关问题