Znajdź następny większy element w tablicy

Question

Biorąc tablicę, dla każdego elementu muszę znaleźć najmniejszy element po prawej stronie danego elementu, który jest większy od bieżącego elementu.

Matematycznie Dla każdego wskaźnika i w tablicy A, trzeba znaleźć wskaźnik j tak, że

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

trzeba znaleźć j dla każdego indeksu i

Bestia roztwór siła byłaby O(n^2) i mam nadzieję, że zrobię to lepiej. Myślę, że rozwiązanie O(n log n) jest możliwe dzięki samonośrodkowemu BST, ale wydaje się to dość skomplikowane. Ponadto potrzebuję rozwiązania O(n).

Czy istnieje rozwiązanie tego problemu w postaci O(n)? Czy istnieje dowód, że dolna granica to O(n log n)?

Answer 1

Dowód O (nlogn) dolnej granicy (na podstawie algorytmów porównywania)

Umożliwia że mamy algorytm porównywania oparte że wykonania tego zadania w O (n). To jest dla każdego indeksu, mamy bezpośrednio większy element po jego prawej stronie (powiedzmy R [i]).

Analogicznie możemy uruchomić ten algorytm na odwróconej macierzy wejściowej, a następnie odwrócić wynik. Dla każdego indeksu mamy bezpośrednio większy element po jego lewej stronie (powiedzmy L [i]).

Oznacza to, że w O (n) mamy dla każdego elementu bezpośredni bezpośredni większy element tablicy = min (R [i], L [i]).

Możemy teraz posortować tablicę, korzystając z tych informacji.

Znajdź minimalny element w tablicy. Znajdź jego następcę (natychmiast większy element), następcę następcy itd. Stąd masz całą tablicę w posortowanej kolejności.

Uporządkował tablicę w O (n), używając tylko porównań (sprzeczność).

O (nlogn) Algorytm:
rozpocząć budowę zrównoważony BST z prawej strony tablicy. Węzły będą zawierać wartości i odpowiednie indeksy.

Następnie dla każdego napotkanego nowego elementu wstawienie go do BST otrzyma odpowiedni najbliższy większy indeks/wartość.