寻找最大值 [英] Finding maximum value

问题描述

千万元素被输入到一个阵列（无存储器约束）。我们知道，虽然进入的元素，我们可以当我们输入一个值检查更新的最大输出输入的值。

Ten million elements are entered into an array (no memory constraints). As we know, while entering the elements we can update the max out of entered values by a check whenever we enter a value.

但想象一下，如果最大值的位置是900万左右的地方

But imagine if the position of max value is somewhere around 9 million

如果我删除位置8 2万台至1000万
没有做任何更多的比较，我们应该有下一个最大值。
将意味着在进入数据，我们应该有一个计划来安排以某种方式获得最大值出来的剩余数据的数据？

If I remove 2 million elements in positions 8 to 10 million without doing any more comparisons, we should have the next maximum value. Will that mean while entering the data we should have a plan to organize the data in some way to get the max value out of the remaining data?

删除和插入会继续发生，但我们应该有更短的时间更新，步数比较少的新/残留的最大值。 （使用多个栈可能的帮助。）

Deleting and inserting will keep on happening, but we should have the new/residual maximum value updated in less time with a smaller number of steps. (Using multiple stacks might help.)

推荐答案

如果块缺失是一个常见的​​操作，您可以维护列表的跨度极大的一个层次。对于每一个编辑你就必须更新这些数据，但是这有点像O（log n）的，而不是0（M log n）的，如果你只是通过并购删除列表中迭代一个接一个从堆中删除它们。

If block deletions are a common operation, you could maintain a hierarchy of maxima of spans of the list. For each edit you then have to update that data, but that's something like O(log n) rather than O(m log n) if you simply iterated through the list of m deletions removing them one-by-one from the heap.

这篇关于寻找最大值的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！