What is the MKAverage problem about?

The MKAverage problem requires calculating an average from a stream of integers, where the smallest and largest `k` elements in the last `m` elements are removed before computing the average.

What is a queue-driven approach in this context?

A queue-driven approach involves maintaining a fixed-size queue of the last `m` elements from the stream, allowing efficient addition of new elements and calculation of the MKAverage.

How do you optimize the calculation of MKAverage?

You optimize the MKAverage calculation by maintaining a running sum of the elements and using efficient data structures like a priority queue to remove the smallest and largest elements.

What are some potential issues in solving the MKAverage problem?

Potential issues include inefficient recalculation of the average or using suboptimal data structures, leading to performance bottlenecks, especially with large streams.

How can GhostInterview help with the MKAverage problem?

GhostInterview provides a structured approach, offering insights into the most efficient data structures and methods for solving the MKAverage problem, reducing the likelihood of common pitfalls.

#1825

Hard

auto_awesome堆

LeetCode 题解工作台

求出 MK 平均值

给你两个整数 m 和 k ，以及数据流形式的若干整数。你需要实现一个数据结构，计算这个数据流的 MK 平均值。 MK 平均值按照如下步骤计算：如果数据流中的整数少于 m 个， MK 平均值为 -1 ，否则将数据流中最后 m 个元素拷贝到一个独立的容器中。从这个容器中删除最小的 k 个数和最…

设计队列堆（优先队列）数据流有序集合

题目描述

给你两个整数 m 和 k ，以及数据流形式的若干整数。你需要实现一个数据结构，计算这个数据流的 MK 平均值 。

MK 平均值 按照如下步骤计算：

如果数据流中的整数少于 m 个，MK 平均值 为 -1 ，否则将数据流中最后 m 个元素拷贝到一个独立的容器中。
从这个容器中删除最小的 k 个数和最大的 k 个数。
计算剩余元素的平均值，并 向下取整到最近的整数 。

请你实现 MKAverage 类：

MKAverage(int m, int k) 用一个空的数据流和两个整数 m 和 k 初始化 MKAverage 对象。
void addElement(int num) 往数据流中插入一个新的元素 num 。
int calculateMKAverage() 对当前的数据流计算并返回 MK 平均数 ，结果需 向下取整到最近的整数 。

示例 1：

输入：
["MKAverage", "addElement", "addElement", "calculateMKAverage", "addElement", "calculateMKAverage", "addElement", "addElement", "addElement", "calculateMKAverage"]
[[3, 1], [3], [1], [], [10], [], [5], [5], [5], []]
输出：
[null, null, null, -1, null, 3, null, null, null, 5]

解释：
MKAverage obj = new MKAverage(3, 1); 
obj.addElement(3);        // 当前元素为 [3]
obj.addElement(1);        // 当前元素为 [3,1]
obj.calculateMKAverage(); // 返回 -1 ，因为 m = 3 ，但数据流中只有 2 个元素
obj.addElement(10);       // 当前元素为 [3,1,10]
obj.calculateMKAverage(); // 最后 3 个元素为 [3,1,10]
                          // 删除最小以及最大的 1 个元素后，容器为 [3]
                          // [3] 的平均值等于 3/1 = 3 ，故返回 3
obj.addElement(5);        // 当前元素为 [3,1,10,5]
obj.addElement(5);        // 当前元素为 [3,1,10,5,5]
obj.addElement(5);        // 当前元素为 [3,1,10,5,5,5]
obj.calculateMKAverage(); // 最后 3 个元素为 [5,5,5]
                          // 删除最小以及最大的 1 个元素后，容器为 [5]
                          // [5] 的平均值等于 5/1 = 5 ，故返回 5

提示：

3 <= m <= 10⁵
1 <= k*2 < m
1 <= num <= 10⁵
addElement 与 calculateMKAverage 总操作次数不超过 10⁵ 次。

lightbulb

解题思路

方法一：有序集合 + 队列

我们可以维护以下数据结构或变量：

一个长度为 $m$ 的队列 $q$ ，其中队首元素为最早加入的元素，队尾元素为最近加入的元素；
三个有序集合，分别为 $lo$ , $mid$ , $hi$ ，其中 $lo$ 和 $hi$ 分别存储最小的 $k$ 个元素和最大的 $k$ 个元素，而 $mid$ 存储剩余的元素；
一个变量 $s$ ，维护 $mid$ 中所有元素的和；
部分编程语言（如 Java, Go）额外维护两个变量 $size1$ 和 $size3$ ，分别表示 $lo$ 和 $hi$ 中元素的个数。

调用 $addElement(num)$ 函数时，顺序执行以下操作：

如果 $lo$ 为空，或者 $num \leq max(lo)$ ，则将 $num$ 加入 $lo$ 中；否则如果 $hi$ 为空，或者 $num \geq min(hi)$ ，则将 $num$ 加入 $hi$ 中；否则将 $num$ 加入 $mid$ 中，同时将 $num$ 的值加到 $s$ 中。
接下来将 $num$ 加入队列 $q$ 中，如果此时队列 $q$ 的长度大于 $m$ ，则将队首元素 $x$ 从队列 $q$ 中移除，接下来从 $lo$ , $mid$ 或 $hi$ 中选择其中一个包含 $x$ 的集合，将 $x$ 从该集合中移除，如果该集合为 $mid$ ，则将 $s$ 减去 $x$ 的值。
如果 $lo$ 的长度大于 $k$ ，则循环将 $lo$ 中的最大值 $max(lo)$ 从 $lo$ 中移除，将 $max(lo)$ 加入 $mid$ 中，同时将 $s$ 加上 $max(lo)$ 的值。
如果 $hi$ 的长度大于 $k$ ，则循环将 $hi$ 中的最小值 $min(hi)$ 从 $hi$ 中移除，将 $min(hi)$ 加入 $mid$ 中，同时将 $s$ 加上 $min(hi)$ 的值。
如果 $lo$ 的长度小于 $k$ ，并且 $mid$ 不为空，则循环将 $mid$ 中的最小值 $min(mid)$ 从 $mid$ 中移除，将 $min(mid)$ 加入 $lo$ 中，同时将 $s$ 减去 $min(mid)$ 的值。
如果 $hi$ 的长度小于 $k$ ，并且 $mid$ 不为空，则循环将 $mid$ 中的最大值 $max(mid)$ 从 $mid$ 中移除，将 $max(mid)$ 加入 $hi$ 中，同时将 $s$ 减去 $max(mid)$ 的值。

调用 $calculateMKAverage()$ 函数时，如果 $q$ 的长度小于 $m$ ，则返回 $-1$ ，否则返回 $\frac{s}{m - 2k}$ 。

时间复杂度方面，每次调用 $addElement(num)$ 函数的时间复杂度为 $O(\log m)$ ，每次调用 $calculateMKAverage()$ 函数的时间复杂度为 $O(1)$ 。空间复杂度为 $O(m)$ 。

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

44

45

46

47

48

49

50

51

52

53

54

class MKAverage:
    def __init__(self, m: int, k: int):
        self.m = m
        self.k = k
        self.s = 0
        self.q = deque()
        self.lo = SortedList()
        self.mid = SortedList()
        self.hi = SortedList()

    def addElement(self, num: int) -> None:
        if not self.lo or num <= self.lo[-1]:
            self.lo.add(num)
        elif not self.hi or num >= self.hi[0]:
            self.hi.add(num)
        else:
            self.mid.add(num)
            self.s += num
        self.q.append(num)
        if len(self.q) > self.m:
            x = self.q.popleft()
            if x in self.lo:
                self.lo.remove(x)
            elif x in self.hi:
                self.hi.remove(x)
            else:
                self.mid.remove(x)
                self.s -= x
        while len(self.lo) > self.k:
            x = self.lo.pop()
            self.mid.add(x)
            self.s += x
        while len(self.hi) > self.k:
            x = self.hi.pop(0)
            self.mid.add(x)
            self.s += x
        while len(self.lo) < self.k and self.mid:
            x = self.mid.pop(0)
            self.lo.add(x)
            self.s -= x
        while len(self.hi) < self.k and self.mid:
            x = self.mid.pop()
            self.hi.add(x)
            self.s -= x

    def calculateMKAverage(self) -> int:
        return -1 if len(self.q) < self.m else self.s // (self.m - 2 * self.k)


# Your MKAverage object will be instantiated and called as such:
# obj = MKAverage(m, k)
# obj.addElement(num)
# param_2 = obj.calculateMKAverage()

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Look for the candidate's understanding of sliding window techniques.
question_mark
Gauge their ability to optimize the insertion and average calculation process.
question_mark
Check if the candidate considers edge cases where `m` is small or the stream has fewer than `m` elements.

warning

常见陷阱

外企场景

error
Not handling cases where the number of elements in the stream is less than `m` before the first `MKAverage` query.
error
Inefficient recalculation of the average by re-sorting or scanning all `m` elements.
error
Overcomplicating the solution by using unnecessary data structures, resulting in unnecessary time or space complexity.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Implement the solution using a deque to avoid sorting and ensure faster operations for average calculation.
arrow_right_alt
Modify the problem to handle updates to the stream where elements can be removed or modified.
arrow_right_alt
Extend the problem to calculate the MKAverage over different window sizes dynamically.

help

常见问题

外企场景

继续练习

#2034 股票价格波动 #2102 序列顺序查询 #1912 设计电影租借系统