替換每個數字，a [i]在其右側有更高的數字，

Question

給定一個整數數組，將每個數字a [i]替換爲右邊更高的數字（根據數值），其值與[i]更接近（如果不存在，則保持原樣）。

例如

輸入 - > 3 7 5

輸出 - > 5 7 5

輸入 - > 3 6 2 6 4 7 1

輸出 - > 4 7 4 7 7 7 1

這個問題在採訪中被問到。

如果從右側開始並在BST中插入每個元素，然後在BST中找到更接近的值，但在最壞的情況下該方法也將爲O（n^2）。

有沒有優化的方法呢？

Answer 1

您可以爲整個數字列表構建均衡的BST。然後，再次通過列表，使用樹找到下一個更大的數字。每個項目完成後，將其從樹中移除。

樹的深度永遠不會增加，所以總的複雜度是O（n log n）用於構建樹，O（log n）用於查找下一個最大項目，O（log n）刪除當前項目。總體O（n log n）沒有花哨的數據結構。