保持排序順序的元素的數據結構支持快速插入和計算連續元素之間的最大差異

Question

我可以將元素存儲在O（logN）插入的STL集合中，並計算O（NlogN）中的最大連續差異。有沒有更快的方法來做到這一點。我不想要代碼。只是一些想法來實現這個DS。謝謝你的幫助。

Answer 1

只需在STL集合上寫一個包裝。每次插入後，插入後，獲取下一個最高密鑰並計算差異。如果它大於當前最大值，請將其替換並存儲添加到此最大值的鍵。

插入仍然是O（log n）。 獲得最大值將是O（1）。

刪除密鑰時，請查看它是否在計算最大差異時使用的密鑰之一。如果是這樣，你必須使最大值失效，並找到新的最大值。只需按排序順序遍歷所有元素，並保持最大運行。在迭代結束時，你會知道O（n）中的最大值。

因此在最壞的情況下刪除O（n）。