首先，我得到一个固定大小的数组，称它为v。 v 的典型大小是几千个条目。我首先计算该数组的最大值。
之后，我会定期获得 v[i] 的新值，并且需要重新计算最大值。
什么是实际快速计算最大值的方法(平均时间)？
编辑:我们可以假设过程是:
1) 统一选择一个随机条目；
2) 将其值更改为[0,1]之间的统一值。
我相信这可以更好地说明问题，并提供明确的“最佳答案”(这将取决于数组大小)。
最佳答案
您可以维护该数组的最大堆。该元素可以是数组的索引。对于数组的每个元素，您还应该有一些指向 max-heap 元素的索引。所以每次v[i]改变，你只需要O(log(n))来维护堆。 (如果 v[i] 增加，它会在堆中上升，如果 v[i] 减少，它会在堆中下降)。
关于algorithm - 运行固定大小的变化数组的最大值，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/33713827/