Trovare il predecessore di ogni elemento di una sequenza

Question

Data una sequenza di a[1], a[2], a[3] .... a[n], devo trovare per ogni a[i], un elemento a[j] dove a[j] è il primo elemento della sequenza a[i - 1], a[i - 2], a[i - 3].... tale che a[j] < a[i].

In altre parole, devo trovare a[j] dove a[j] < a[i] e 1<=j<i. Ma se ci sono più di questi elementi, devo scegliere quello che è più vicino a a[i].

Ad esempio, nella seguente sequenza:

2 6 5 8

devo uscita 2 sia per 6 e 5, e 5 per 8.

So che questo può essere fatto facilmente in O(n^2) , ma esiste un modo più efficiente per farlo?

Answer 1

Può essere fatto in O(n) utilizzando un stack.

a = your array 
d = a stack 
d.push(a[1]) 
for i = 2 to n do 
    while d.top > a[i] do 
    d.pop() 

    print d.top if it exists, else -1 
    d.push(a[i]) 

In sostanza, continuiamo d ordinato e assicurarsi che il suo ultimo elemento è sempre più piccolo di a[i]. In questo modo, l'ultimo elemento in d sarà sempre quello che stiamo cercando.

La complessità lineare potrebbe non essere immediatamente evidente a causa dei cicli nidificati, ma osservare che ogni elemento lascerà ed entrerà nella pila al massimo una volta, quindi un numero costante di volte.