Найти следующий больший элемент в массиве

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

Математически Для каждого индекса i в массиве A мне нужно найти индекс j такой, что

Решение грубой силы будет O(n^2), и я надеюсь сделать лучше. Я думаю, что решение O(n log n) возможно с использованием самобалансирующегося BST, но это кажется довольно сложным. Кроме того, мне нужно решение O(n).

Есть ли решение этой проблемы? Существует ли доказательство того, что нижняя грань O(n log n)?

Ответы

Ответ 1

Доказательство нижней границы O (nlogn): (для алгоритмов сравнения)

Допустим, у нас есть алгоритм на основе сравнения, который выполнил бы эту задачу в O (n). То есть для каждого индекса у нас есть правый элемент справа (скажем, R [i]).

Аналогично, мы можем запустить этот алгоритм на обратном входном массиве и затем отменить результат. Для каждого индекса у нас есть ближайший большой элемент слева (например, L [i]).

Это означает, что в O (n) для каждого элемента мы имеем непосредственный старший элемент в массиве = min (R [i], L [i]).

Теперь мы можем отсортировать массив, используя эту информацию.

Найти минимальный элемент в массиве. Найдите его преемника (ближайший больший элемент), затем его преемника-преемника и т.д. Следовательно, вы получили бы весь массив в отсортированном порядке.

Отсортировано массив в O (n), используя только сравнения (противоречие).

O (nlogn) Алгоритм:
Начните строить сбалансированный BST справа от массива. Узлы будут содержать значения и соответствующие индексы.

Затем для каждого нового найденного элемента вставка его в BST получит соответствующий ближайший больший индекс/значение.