在数组中寻找最大值

将一千（1000）个元素输入到数组中（无内存约束）。我们知道，输入元素时，只要输入值，我们就可以通过检查来更新输入值中的最大值。在数组中寻找最大值

但想象一下，如果最大值的位置是某处大约900

如果我从位置取出200元800〜1000，没有做任何更多的比较，我们应该有下一个最大值。这意味着在输入数据时我们应该有一个计划来组织数据以某种方式从剩余数据中获取最大值？

删除和插入操作将继续进行，但我们应该在更少的时间内更新最大值，而不需要更少的步骤。（使用堆栈可能有帮助，是面试官给我的线索）。任何人都请帮助我。

使用二进制最大堆！ – skrtbhtngr

这与[寻找最大值]（http://stackoverflow.com/questions/30689110/）的缩小版非常相似。主要区别在于，另一个问题是处理1千万（1000万）元素和删除20万（200万）元素。 –

我们是否可以假设删除/添加仅允许在数组的末尾，或者您是否可以从1000的数组中移除元素850到950？ – user3386109

最大的堆可能适用于您的情况。但是因为1000非常小，所以你可能不需要复杂的东西。

2015-06-07 05:30:53

这1000可以达到1千分之一。 –

你能否请我解释一下如何使用最大堆。我是计算机科学新生。 –

http://en.wikipedia.org/wiki/Binary_heap –

在数组上创建一个树形结构。在每个节点中保留子树的范围和最大值。在删除/插入时，自下而上更新受影响节点中的最大值。

2015-06-07 05:38:19

您应该使用max heap数据结构。 max-heap的财产是你可以在O(1)时间获得最大值。而每个插入和删除将花费O(log(n))时间。欲了解更多信息，请查阅here

2015-06-07 06:41:16

回答