Trova il prossimo elemento più grande in un array

Question

Dato un array, per ogni elemento ho bisogno di trovare l'elemento più piccolo a destra dell'elemento dato che è maggiore dell'elemento corrente.

Matematicamente, Per ogni indice i in ordine A, ho bisogno di trovare indice j tale che

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

Ho bisogno di trovare j per ogni indice i

La soluzione di forza bruta sarebbe O(n^2) e spero di fare meglio. Sto pensando che una soluzione O(n log n) sia possibile usando il BST autobilanciato ma sembra piuttosto complesso. Inoltre ho bisogno di una soluzione O(n).

Esiste una soluzione O(n) a questo problema? C'è una prova che il limite inferiore è O(n log n)?

Answer 1

Prova di O (nlogn) limite inferiore: (per algoritmi basati confronto)

Consente di dire che abbiamo un algoritmo di confronto-based che sarebbe svolgere questo compito in O (n). Questo è per ogni indice, abbiamo l'elemento immediatamente più grande alla sua destra (diciamo R [i]).

Analogamente, è possibile eseguire questo algoritmo sulla matrice di input invertita e invertire il risultato. Per ogni indice abbiamo l'elemento immediatamente più grande alla sua sinistra (diciamo L [i]).

Ciò significa che in O (n) abbiamo per ciascun elemento, l'elemento immediatamente più grande nella matrice = min (R [i], L [i]).

Ora possiamo ordinare l'array utilizzando queste informazioni.

Trova l'elemento minimo dell'array. Trova il suo successore (elemento immediatamente più grande), quindi il successore del successore ecc. Quindi avresti ottenuto l'intero array in ordine.

Ordinato l'array in O (n) utilizzando solo confronti (una contraddizione).

O (nlogn) Algoritmo:
avviare la costruzione del BST equilibrato da destra dell'array. I nodi conterrebbero i valori e i rispettivi indici.

Quindi, per ogni nuovo elemento rilevato, inserendolo nel BST si ottiene il corrispondente più grande indice/valore.