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

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

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

A[j] > A[i]
j > i
A[j] - A[i] is minimum

Мне нужно найти j для каждого индекса i

Решение грубой силы будет 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 получит соответствующий ближайший больший индекс/значение.