更新时间:2022-12-08 19:06:04
最简单的解决方案是从右到左遍历输入,对于每个元素,查找树中第一个更大的元素(或具有O(LogN)查找和插入的任何数据结构),然后将该元素添加到树中。这样,更大的元素将始终位于输入中的元素之后。
The simplest solution is to iterate over the input from right to left, and for each element look up the first greater element in a tree (or any data structure with O(LogN) look-up and insertion), and then add the element to the tree. That way the greater element always comes after the element in the input.
对于C ++版本,可以使用 std :: map
,其中元素的值是键,而元素在输入中的索引为值,并使用 upper_bound
获取下一个更大的值:
For a C++ version, you can use a std::map
where the element's value is the key and the element's index in the input is the value, and use upper_bound
to get the next greater value:
#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;
}