Câte zile până la o zi mai caldă
Ai temperaturile pe mai multe zile și vrei să știi, pentru fiecare zi, câte zile aștepți până vine una mai caldă. Forța brută este O(n²). Cu o stivă monotonă de indici rezolvi totul într-o singură parcurgere, O(n).
Problema
Primești lista t cu temperaturi zilnice. Pentru fiecare zi i vrei numărul de zile până la prima zi j > i cu t[j] > t[i]. Dacă nu există, rezultatul e 0.
Scrie funcția zile_pana_la_cald(t) care returnează lista cu numărul de zile de așteptat pentru fiecare zi (0 dacă nu vine o zi mai caldă), folosind o stivă monotonă de indici, în O(n).
- Pornește cu rez = [0] * len(t) și o stivă goală.
- Pentru fiecare i: while stiva and t[i] > t[stiva[-1]], scoți j și pui rez[j] = i - j.
- Apoi stiva.append(i). Trebuie să apară: [1, 1, 4, 2, 1, 1, 0, 0], [1, 1, 1, 0], [0, 0, 0], [0, 0].
Restul explicațiilor, editorul și verificarea automată se deblochează cu Hash map, stive, cozi și liste înlănțuite.

Alex Cristian
Iulian Pahom
Catalina Ioana Dan