algorithm - 保持容器的最大值。

Question

假设我有一长串值。我知道最大值所在的索引。

在每一步中，我都会在一定的条件下选择一个值，并根据一些规则对其进行修改(这里不重要)。每次修改后，我都必须知道数组的最大值。

最简单的方法是比较修改后的值N和之前的最大值O，如果N > O则更新最大值为N。但是，如果修改的索引是先前存储最大值的位置，事情就会变得棘手。在这种情况下，我需要扫描数组并找出最大值是什么，即 O(L)，其中 L 是数组的长度。我想避免这种最坏情况的复杂性。

实现它的最佳方法是什么？ (算法还是数据结构？)

Answer 1

存储“先前”的先前最大值 (P)，并在 N 和 O 为相同索引时将 N 与该值进行比较。 P被N取代为当前的最大值，所以如果N降低到P的值以下，那么P应该再次成为最大值。