我有一个任务,要求我找到所有数组条目中数组中所有较大元素中最小的元素,并将相应的索引存储在一个数组中,我无法弄清楚解决方案的最后部分.

这有点类似于这里解释的问题：
https://www.geeksforgeeks.org/smallest-greater-elements-in-whole-array/

唯一的区别是只考虑数组条目的右边的值(j> i),例如：

input:  [80; 19; 49; 45; 65; 71; 76; 28; 68; 66]  
output: [-1;  7;  4;  4;  9;  6; -1;  9; -1; -1]

使用自平衡树的解决方案对我来说很有意义.但是,我仍然需要考虑索引,因为只有数组条目的解决方案才有效.

有没有办法将插入值的索引映射到树条目或创建第二个树具有相同的结构,但旧数组条目的索引而不是实际值作为节点？我不确定,因为自平衡树的结构当然取决于插入的值(更大的值右子树,更小的值留下子树).

编辑：实际上第二个AVL树可能无济于事,因为我必须检查索引是否更大并且在遍历树时数组条目更大…

解决方法:

最简单的解决方案是从右到左迭代输入,并为每个元素查找树中的第一个更大元素(或任何具有O(LogN)查找和插入的数据结构),然后将元素添加到那个树.这样,更大的元素总是在输入中的元素之后.

对于C版本,您可以使用std :: map,其中元素的值是键,输入中元素的索引是值,并使用upper_bound获取下一个更大的值：

#include <iostream>
#include <vector>
#include <map>

void nextValues(std::vector<int> &in, std::vector<int> &out) {
    std::map<int, int> tree;
    for (int i = in.size() - 1; i >= 0; i--) {
        out.insert(out.begin(), tree.upper_bound(in[i])->second - 1);
        tree.insert(std::pair<int, int>(in[i], i + 1));
    }
}

int main() {
    std::vector<int> a = {80,19,49,45,65,71,76,28,68,66};
    std::vector<int> b;
    nextValues(a, b);
    for (int i : b) std::cout << (int) i << ","; // -1,7,4,4,9,6,-1,9,-1,-1
    return 0;
}