algorithm - 运行固定大小的变化数组的最大值

Question

首先，我得到一个固定大小的数组，称它为v。 v 的典型大小是几千个条目。我首先计算该数组的最大值。

之后，我会定期获得 v[i] 的新值，并且需要重新计算最大值。

什么是实际快速计算最大值的方法(平均时间)？

编辑:我们可以假设过程是:

1) 统一选择一个随机条目；

2) 将其值更改为[0,1]之间的统一值。

我相信这可以更好地说明问题，并提供明确的“最佳答案”(这将取决于数组大小)。

Answer 1

您可以维护该数组的最大堆。该元素可以是数组的索引。对于数组的每个元素，您还应该有一些指向 max-heap 元素的索引。所以每次v[i]改变，你只需要O(log(n))来维护堆。 (如果 v[i] 增加，它会在堆中上升，如果 v[i] 减少，它会在堆中下降)。