Нахождение наименьшего следующего большего элемента

Question

У меня есть задача, которая требует от меня найти наименьший из всех более крупных элементов в массиве для всех элементов массива и сохранить соответствующие индексы в массиве, и я не могу понять последнюю часть решения.

Это похоже на проблему, описанную здесь: 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, вероятно, не поможет, так как я должен проверить, что индексирование больше, а запись массива больше при обходе дерева ...

Answer 1

Самое простое решение - перебрать ввод справа налево, и для каждого элемента найти первый больший элемент в дереве (или любую структуру данных с поиском и вставкой 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;
}