Următorul element mai mare
Aceeași stivă monotonă din lecția trecută rezolvă o întreagă familie de probleme. Azi cauți, pentru fiecare element, primul element mai mare din dreapta lui, apoi faci același lucru pe o listă circulară, unde după ultimul element urmează din nou primul.
Problema
Pentru fiecare poziție i vrei valoarea primului element din dreapta care este strict mai mare decât lista[i]. Dacă nu există, rezultatul este -1.
Scrie două funcții cu stivă monotonă: urmatorul_mai_mare(lista) (lista obișnuită) și urmatorul_mai_mare_circular(lista) (lista este un cerc). Ambele returnează valoarea primului element strict mai mare din dreapta, sau -1.
- În ambele funcții pornește cu rez = [-1] * n și o stivă de indici.
- În varianta circulară parcurge range(2 * n), cu lista[i % n], și pune pe stivă doar când i < n.
- Trebuie să apară: [5, 25, 25, -1], [-1, 12, 12, -1], [2, -1, 2], [-1, 2, 3, 3].
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