Algorithmen und Datenstrukturen · Middle · Frage 21 von 75
Wofür nutzt man einen monotonen Stack?
- 1Eine Queue auf Basis zweier Stacks umsetzen
- 2Nächstgrößeres Element für jedes Element in O(n)
- 3Ein Zahlen-Array in O(n) Zeit sortieren
Antwort zeigen
Richtige Antwort: Nächstgrößeres Element für jedes Element in O(n)
Erklärung
Der Stack hält Indizes mit fallenden Werten. Kommt ein größerer Wert, nimmt er die kleineren herunter: der neue Wert ist ihr „nächstgrößeres“ Element. Jeder Index wird einmal abgelegt und einmal genommen, der Durchlauf ist also O(n).