Stiva monotonă păstrează valori în loc de indici: distanțele ies greșite
Dacă pui în stivă valorile, nu mai știi pe ce poziție era fiecare, iar lista.index(v) găsește prima apariție, nu pe cea corectă. Pune în stivă indicii (stiva.append(i)) și compară cu t[stiva[-1]].
Explicat de Tudor Andrei Dumitrescu, Senior Software Developer, fondatorul Academiei ProgramatorilorActualizat la
Ce înseamnă
Stiva monotonă rezolvă în O(n) probleme ca „câte zile până la o temperatură mai mare”, „următorul element mai mare” sau „cel mai mare dreptunghi din histogramă”. Pentru majoritatea ai nevoie de distanțe sau poziții, deci în stivă trebuie ținuți indicii.
Dacă păstrezi valorile, după pop() trebuie să afli de unde venea valoarea. t.index(v) returnează mereu prima apariție a lui v, deci la valori repetate scrie rezultatul pe poziția greșită, iar poziția corectă rămâne 0. În plus, index e O(n), deci tot algoritmul devine O(n²).
Nu primești nicio eroare. Pe date fără valori repetate rezultatul pare corect, de aceea testul trebuie să conțină duplicate.
De ce apare: cauzele frecvente
1Valori în stivă, poziția căutată cu index()
while stiva and stiva[-1] < x:
v = stiva.pop()
j = t.index(v)
rez[j] = i - j
stiva.append(x)while stiva and t[stiva[-1]] < x:
j = stiva.pop()
rez[j] = i - j
stiva.append(i)Cu indici în stivă, fiecare element își știe poziția exactă, iar valoarea se citește cu t[j].
2Ai nevoie și de valoare, și de poziție
stiva.append(pret)stiva.append((pret, i))O pereche (valoare, index) păstrează ambele informații fără căutări.
Repară eroarea, direct în pagină
Funcția zile_pana_la_cald(t) calculează, pentru fiecare zi, după câte zile vine o temperatură mai mare (0 dacă nu vine). Stiva păstrează temperaturile, iar testul cu assert pică la valori repetate. Repar-o ca să afișeze [1, 3, 2, 1, 0].
def zile_pana_la_cald(t):
rez = [0] * len(t)
stiva = []
for i, x in enumerate(t):
while stiva and stiva[-1] < x:
v = stiva.pop()
j = t.index(v)
rez[j] = i - j
stiva.append(x)
return rez
rez = zile_pana_la_cald([70, 71, 70, 69, 72])
assert rez == [1, 3, 2, 1, 0], f'zile gresite: {rez}'
print(rez)[1, 3, 2, 1, 0]
Indiciu
Pune în stivă indicii zilelor și compară cu t[stiva[-1]].
Reparația
def zile_pana_la_cald(t):
rez = [0] * len(t)
stiva = []
for i, x in enumerate(t):
while stiva and t[stiva[-1]] < x:
j = stiva.pop()
rez[j] = i - j
stiva.append(i)
return rez
rez = zile_pana_la_cald([70, 71, 70, 69, 72])
assert rez == [1, 3, 2, 1, 0], f'zile gresite: {rez}'
print(rez)De ce merge
Temperatura 70 apare în zilele 0 și 2. Când a venit 72, varianta veche a scos 70 din stivă și a căutat-o cu t.index(70), care dă mereu ziua 0: a suprascris rez[0] și a lăsat ziua 2 cu 0. Cu indici în stivă, fiecare element scos își știe ziua exactă, deci distanța i - j ajunge pe poziția corectă.
Cum o eviți pe viitor
Când răspunsul depinde de distanțe sau poziții, pune în stivă (sau în coadă, sau în heap) indicii. Valoarea o citești oricând din listă. Evită lista.index(...) în bucle: e lent și greșit la duplicate. Testează pe o listă cu valori repetate în poziții diferite.
Întrebări frecvente
Stiva trebuie să fie crescătoare sau descrescătoare?
Depinde de întrebare. Pentru „următorul mai mare”, stiva ține valori descrescătoare (indicii lor): când vine o valoare mai mare, scoți tot ce e mai mic.
De ce e O(n) dacă am un while în for?
Fiecare index intră în stivă o dată și iese cel mult o dată, deci totalul operațiilor din while e cel mult n.
Erori înrudite
Verificarea parantezelor returnează True pentru „((” (stiva rămâne nevidă) Funcția verifică doar parantezele închise, dar la final nu verifică dacă au rămas paranteze deschise în stivă. Înlocuiește return True de la final cu return not stiva (sau len(stiva) == 0). IndexError: pop from empty list Ai apelat stiva.pop() pe o stivă goală. La verificarea parantezelor înseamnă de obicei o paranteză închisă fără pereche. Verifică înainte cu if not stiva: (și tratează cazul) sau pune condiția în while stiva and ... Time Limit Exceeded: x in lista într-o buclă face soluția O(n²) x in lista caută element cu element (O(n)), iar într-o buclă peste n elemente devine O(n²): pe date mari programul depășește limita de timp. Transformă lista în set o singură dată (set_b = set(b)), apoi x in set_b e O(1) în medie. Învață Algoritmi și structuri de date de la zero, cu exerciții la fiecare lecție
Curs Algoritmi pentru interviuri: lecții scurte, fiecare cu un exercițiu verificat automat, direct în browser. Primele 2 lecții sunt gratuite.
