...
Eroare Algoritmi și structuri de date · Stive, cozi și liste înlănțuite

Stiva monotonă păstrează valori în loc de indici: distanțele ies greșite

Pe scurt

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()

Greșit
PYTHON
while stiva and stiva[-1] < x:
    v = stiva.pop()
    j = t.index(v)
    rez[j] = i - j
stiva.append(x)
Corect
PYTHON
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

Greșit
PYTHON
stiva.append(pret)
Corect
PYTHON
stiva.append((pret, i))

O pereche (valoare, index) păstrează ambele informații fără căutări.

Repară tu

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].

Codul care dă eroarea
PYTHON
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)
După reparație, programul afișează
[1, 3, 2, 1, 0]
Indiciu

Pune în stivă indicii zilelor și compară cu t[stiva[-1]].

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

← Toate erorile Algoritmi și structuri de date

Tudor Andrei Dumitrescu
Cine a explicat eroarea

Tudor Andrei Dumitrescu

Senior Software Developer · fondatorul Academiei Programatorilor

LinkedIn
  1. 2019 Junior JavaCognizant Softvision
  2. 2021 Mid JavaCognizant Softvision
  3. 2022 Team LeaderEndava
  4. 2023 Senior Software DeveloperUniCredit
  5. Acum Senior Software DeveloperHCLTech
Certificat de absolvire Instructor / Preparator formare, Tudor Andrei Dumitrescu
Certificat de formator autorizatMinisterul Muncii și Ministerul Educației · 2022
Certificat de absolvire Instructor / Preparator formare, Tudor Andrei Dumitrescu

Certificat de formator autorizat · Ministerul Muncii și Ministerul Educației · 2022

Din 2020 construiește Academia Programatorilor, iar din 2026 și JoburiIT.ro. Fiecare eroare de aici a fost reprodusă în editorul nostru: codul greșit chiar dă mesajul din titlu, iar reparația chiar funcționează.

Î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.