如何在任意大小的窗口中跟踪最高值和最低值

Question

我有一个音频输入流，它接收播放音乐的当前音量。然后，在最新卷的特定窗口大小(范围从 5 到 40(上，我想跟踪窗口内的最高值和最低值。因此，在每次迭代中，都会删除添加的最旧值，并添加最新的音量级别读数。

假设我在 5 个窗口内运行程序 8 次迭代，这将产生。只有低值和高值很重要。

加 2

阿拉伯数字

添加 4

2 4

添加 3

2 3 4

加 2

2

2 3 4

添加 7

2

2 3 4 7

-前 2 个从列表中删除，添加 9

个

2 3 4 7 9

4 删除，添加 5

2 3 5 7 9

3 删除，添加 2

2

2 5 7 9

等

执行此操作以及使用哪种类型的集合的最有效方法是什么？

编辑请注意，此循环在单独的线程上不断运行

值为浮点数

Answer 1

在每次迭代中，都会添加和删除一个数字，然后添加和删除最小值和 最大发现，它们出现相同的数量

使用平衡的二叉树，如树状图，所以在最坏的情况下，所有操作都将是O(log n(。我相信，如果这些操作成功发生，那么 3 个操作是 O(1( 和一个是 O(n( 是没有意义的。

顺便说一句，n=5 是如此之小，我不明白为什么你应该太担心效率低下。

编辑：要跟踪对象的顺序，您可以使用简单队列作为辅助结构。当您需要删除时，您可以删除队列的头部，并将其用作在树中删除的键。添加和删除需要恒定的时间。

注：可以到此为止，原意如下

一个更好的复杂性数据结构将是一个调整的最小-最大堆，它提供了所有操作之间的良好权衡：

• 插入O(log n)
• 删除是O(n)
• 敏和马克斯都是O(l)。

如果仅删除最大值/最小值，则删除将是对数的。调整是实现一个通用的删除，即log n

Answer 2

您可以使用链表，因为您希望在列表中存储重复的值。另外，由于您计划添加到最后一个元素，因此请使用LinkedList API的addLast((方法。在你自己的add((方法中，检查大小。如果大小达到最大大小，则可以调用链接列表的 removeFirst(( 方法，然后调用 addLast(( 方法。这样，您的链接列表大小将保持不变，为 5

public class Tester {
private LinkedList<Integer> values = new LinkedList<Integer>();
private static final int MAX_VAL = 5;
public void addvalue(int val) {
    if (values.size() == this.MAX_VAL) {
        values.removeFirst();
    }
    values.addLast(val);
}
public int getMaxValue(){           
    return Collections.min(values);
}
public int getMinValue(){
    return Collections.max(values);
}

}

Answer 3

由于值是整数 5 到 40，如果窗口很大，我们可以通过存储数组count[]来尝试获得良好的平均案例时间，该数组会记录每个卷的窗口数。然后添加新元素并删除最后一个元素(保留Queue如 LinkedList (是恒定时间，除非 low 或 high 处的计数下降到 0。然后从最后一个最佳开始逐个搜索值，这很O(35)，但在实践中可能会更便宜，尤其是在大窗口的情况下。

在某种程度上，这是一个恒定时间解决方案，在实际输入中，您添加的体积元素的数量。这O(nk)听起来k只有三十几卷。我怀疑我们可以证明平均案例时间是Theta(nk/w)，其中w是窗口大小，假设数据分布合理。

这听起来真的不像是一个高吞吐量的操作(用户多久可以更改一次卷，所有数百次？？(，但这就是我在这些条件下实现它的方式。