Stiva care știe minimul în O(1)
Un clasic de interviu: construiește o stivă care, pe lângă push și pop, îți spune oricând cel mai mic element din ea, tot în O(1). Trucul este o a doua stivă care ține minte minimul de până acum.
Problema
Vrei o clasă StivaMin cu patru operații, toate O(1): push(x) adaugă, pop() scoate vârful, top() citește vârful, minim() returnează cel mai mic element din stivă.
Completează clasa StivaMin cu metodele push, pop, top și minim, toate O(1), folosind o a doua listă self.minime. Testul face: push 5, push 2, push 8, afișează minimul, pop, pop, afișează minimul, apoi vârful.
- În push, adaugă în self.minime minimul dintre x și vârful lui self.minime (sau x dacă e goală).
- În pop, scoate din ambele liste și returnează elementul din self.stiva.
- minim() returnează vârful lui self.minime. Trebuie să apară: 2, 5, 5.
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