Algorytmy i struktury danych · Middle · Pytanie 21 z 75
Do czego służy stos monotoniczny?
- 1Implementacja kolejki na dwóch stosach
- ✓Poprawna odpowiedź: Następny większy element dla każdego elementu w O(n)
- 3Sortowanie tablicy liczb w O(n)
Wyjaśnienie
Stos trzyma indeksy o malejących wartościach. Gdy przychodzi większa wartość, zdejmuje mniejsze: nowa wartość jest ich „następnym większym” elementem. Każdy indeks jest wkładany i zdejmowany raz, więc przejście to O(n).