数据流题库

数据流中的移动平均值

给定一个整数数据流和一个窗口大小，根据该滑动窗口的大小，计算其所有整数的移动平均值。

实现 MovingAverage 类：

• MovingAverage(int size) 用窗口大小 size 初始化对象。
• double next(int val) 计算并返回数据流中最后 size 个值的移动平均值。

示例:

输入：
["MovingAverage", "next", "next", "next", "next"]
[[3], [1], [10], [3], [5]]
输出：
[null, 1.0, 5.5, 4.66667, 6.0]

解释：
MovingAverage movingAverage = new MovingAverage(3);
movingAverage.next(1); // 返回 1.0 = 1 / 1
movingAverage.next(10); // 返回 5.5 = (1 + 10) / 2
movingAverage.next(3); // 返回 4.66667 = (1 + 10 + 3) / 3
movingAverage.next(5); // 返回 6.0 = (10 + 3 + 5) / 3

方案A 通过循环队列

思路: 循环队列的主要优点是，通过向循环队列中添加新元素，它会自动丢弃最旧的元素。

• 实现具有固定大小数组的循环队列:
  • head:头指针
  • tial:尾指针 (head+1) % size

:::details 点击查看代码

function MovingAverage(size) {
    this.length=0;
    this.capacity=size;
    this.headIndex=0;
    this.windowSum=0;
    this.queue=new Array(size).fill(0);
};

MovingAverage.prototype.next = function(val) {
    this.length++;
    let tailIndex=(this.headIndex+1)%this.capacity;
    this.windowSum=this.windowSum-this.queue[tailIndex]+val;
    this.headIndex=(this.headIndex+1)%this.capacity;
    this.queue[this.headIndex]=val;
    return this.windowSum/Math.min(this.capacity,this.length);
};

:::

性能分析:

时间复杂度：O(1)。我们可以看到在 next(val) 函数中没有循环。 空间复杂度：O(N)，循环队列使用的大小。

数据流中的第 K 大元素

设计一个找到数据流中第 k 大元素的类（class）。注意是排序后的第 k 大元素，不是第 k 个不同的元素。

请实现 KthLargest 类：

• KthLargest(int k, int[] nums) 使用整数 k 和整数流 nums 初始化对象。
• int add(int val) 将 val 插入数据流 nums 后，返回当前数据流中第 k 大的元素。

示例:

输入：
["KthLargest", "add", "add", "add", "add", "add"]
[[3, [4, 5, 8, 2]], [3], [5], [10], [9], [4]]
输出：
[null, 4, 5, 5, 8, 8]

解释：
KthLargest kthLargest = new KthLargest(3, [4, 5, 8, 2]);
kthLargest.add(3);   // return 4
kthLargest.add(5);   // return 5
kthLargest.add(10);  // return 5
kthLargest.add(9);   // return 8
kthLargest.add(4);   // return 8

方案A 堆思想

思路:

• 使用大小为 K 的小根堆，在初始化的时候，保证堆中的元素个数不超过 K 。
• 在每次 add() 的时候，将新元素 push() 到堆中，如果此时堆中的元素超过了 K，那么需要把堆中的最小元素（堆顶）pop() 出来。
• 此时堆中的最小元素（堆顶）就是整个数据流中的第 K 大元素。

问题:

• 为什么使用小根堆？

因为我们需要在堆中保留数据流中的前 K 大元素，使用小根堆能保证每次调用堆的 pop() 函数时，从堆中删除的是堆中的最小的元素（堆顶）

• 为什么能保证堆顶元素是第 K 大元素？

因为小根堆中保留的一直是堆中的前 K 大的元素，堆的大小是 K，所以堆顶元素是第 K 大元素。

• 每次 add() 的时间复杂度是多少？

每次 add() 时，调用了堆的 push() 和 pop() 方法，两个操作的时间复杂度都是 log(K).

:::details 点击查看代码

class MinHeap{
    head=[];
    length=0;
    push(value){
        this.head.push(value);
        this.length++;
        if(this.length!=1){
            this.shiftUp(this.length-1);
        }
    }
    shiftUp(index){
        while(index>0){
            let parent=Math.floor((index-1)/2);
            if(this.head[index]<this.head[parent]){
                [this.head[index],this.head[parent]]=[this.head[parent],this.head[index]];
                index=parent;
            }else{
                return 
            }
        }
    }
    pop(){
        this.head[0]=this.head.pop();
        this.length--;
        this.shiftDown(0);
    }
    shiftDown(index){
        while(index*2+1<=this.length-1){
            let child=index*2+1;
            if(child+1<=this.length-1&&this.head[child]>this.head[child+1]){
                child++;
            }
            if(this.head[index]>this.head[child]){
                [this.head[index],this.head[child]]=[this.head[child],this.head[index]];
                index=child;
            }else{
                return;
            }
        }
    }
}

function KthLargest(k, nums) {
    this.k=k;
    this.minHeap=new MinHeap();
    for(let item of nums){
        this.add(item);
    }
};
KthLargest.prototype.add = function(val) {
    this.minHeap.push(val);
    if(this.minHeap.length>this.k){
        this.minHeap.pop();
    }
    return this.minHeap.head[0];
};

:::

性能分析:

• 时间复杂度:
  • 初始化时间复杂度为：O(nlogk) ，其中 n 为初始化时 nums 的长度；
  • 单次插入时间复杂度为：O(logk)。
• 空间复杂度: O(k)。需要使用数组存储前 k 大的元素。