保持容器的最大值。

假設我有很多數值。我知道最大價值的指數。保持容器的最大值。

在每個步驟中，我會根據某些標準選擇一個值並根據一些規則對其進行修改（這裏不重要）。每次修改後，我必須知道數組的最大值。

的最簡單的方法是比較修改的值N和先前最大值O並且如果N > O然後更新最大值作爲N。然而，如果被修改的索引是先前最大值的存儲位置，那麼情況會變得棘手。在這種情況下，我需要掃數組，並找出O(L)的最大值是多少，其中L是數組的長度。我想避免這種最糟糕的情況下的複雜性。

實現它的最好方法是什麼？（算法或數據結構？）

2013-05-30 Sungmin

一個字：堆。 –

兩個字：堆排序。 – Jason

一個鏈接：http://stackoverflow.com/questions/7134129/stack-with-find-min-find-max-more-efficient-than-on – 0x90

-2

當N和O是相同的索引時，存儲「前一個」先前的最大值（P）並將N與該值進行比較。 P被N取代爲當前最大值，所以如果N減少到P的值以下，則P應該再次成爲最大值。

2013-05-30 04:55:12 huene

但現在你必須找到一個新的P.這並不能解決任何問題。 –

您不處理僅刪除插入的情況。 – 0x90

@Emil - 你說得對。 N可以被修改，使其不會是「P」後面的第二高值，導致需要搜索新的「P」......沒有想到這一點。 – huene

回答