如何处理BST问题？

Question

我遇到了这个问题：

您将获得一个由 n 个不同的整数 a0、a1、. . .an−1.在每次迭代中，您选择最大数字并将其删除，取消最大数字的成本是其左侧的数字数。重复此 n 次。给定ai实现一个O（n log n）算法来计算n次迭代的总成本。

我知道我们必须使用BST来解决这个问题，因为它是O（N log N），但是，我不知道该怎么办。

我想我可以在hashMap中存储值和索引，当删除完成后，我们在BST中搜索该索引，并在遍历的路径中添加索引值。但是，在删除节点时，我们必须减少所有索引的 BST 索引值

我不确定这是否可行，我希望得到任何建议/指导：）

Answer 1

虽然@0x499602D2注释是正确的，但排序是正确的方法。这个问题是合并排序的另一个应用，类似于计数反转。

从右边合并一个元素会减少左边剩余元素的数量（您知道为什么吗？）。数组完全排序后，成本降到0。

我希望这足以让你开始。