有誰知道陣列最后n個條目的最大值（或最小值）的有效增量演算法？
“高效”和“增量”是指當一個新元素被添加到陣列中時，我們會做一些比僅僅搜索最后n個條目的最大值更聰明的事情！理想情況下，它應該是關于n的恒定復雜度 O(1) （當然 < O( n )）。顯然，每個陣列條目都可以存盤一個或多個資料以幫助計算。計算的最大值必須可用于所有陣列條目，而不僅僅是最后一個條目。
謝謝
uj5u.com熱心網友回復：
你很幸運，由于 van Herk、Gil 和 Werman 有一個很酷的演算法，它可以在每個元素的恒定時間內計算一維膨脹。
https://tpgit.github.io/UnOfficialLeptDocs/leptonica/grayscale-morphology.html
可以使用 2N-1 個元素的緩沖區在線制作。
這個想法很簡單。如果要計算四個連續元素的最大值，可以遞增計算以下最大值：a, ab, abc,abcd和e, ef, efg, efgh。現在結合...
abcd
bcd e
cd ef
d efg
并重復以下元素。
uj5u.com熱心網友回復：
這是一個想法，它可以在恒定時間內為您提供陣列的最后 n 個元素的最小值和最大值，并且添加新元素具有O(log n)時間復雜度。
- 有一個最小和一個最大堆，用于保存
n陣列的最后一個元素。這些元素需要是您以后可以參考的節點。 - 具有鏈表形式的佇列或 FIFO 操作具有恒定時間復雜度的任何資料結構。跟蹤
n此佇列中的最后一個元素。佇列的每個元素都包含對最小和最大堆中相應條目的參考。 - 每當向陣列中添加新元素時，請執行以下操作：
- 將其添加到最小和最大堆：
log n操作。 - 將對佇列中這個新元素的參考加入佇列：常量操作。
- 將佇列中超出
n長度視窗的元素的參考從佇列中取出：常量操作。 - 從最小和最大堆中洗掉該元素：
log n操作。
n最小和最大堆在恒定時間內隨時為您提供最后一個元素的當前最小和最大元素。
但是，一種不會改變時間復雜度的可能優化是將洗掉和添加操作合并到一個堆中為一個步驟。您要做的是用新元素的值更新要從堆中洗掉的參考的值。然后為堆運行游泳和下沉操作以保持其不變數。然后，您將再次將 dequed 參考加入佇列，因為它現在保存n長度視窗中的最新值。
轉載請註明出處，本文鏈接：https://www.uj5u.com/qianduan/417238.html
標籤：
下一篇：深度優先搜索的發現時間和完成時間