最简单的解决方案是从右到左遍历输入，对于每个元素，查找树中第一个更大的元素（或具有O（LogN）查找和插入功能的任何数据结构），然后将该元素添加到那个树。这样，更大的元素将始终位于输入中的元素之后。
对于C ++版本，可以使用a
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;}
