Алгоритми та структури даних · Middle · Запитання 21 з 75
Для чого використовують монотонний стек?
- 1Реалізація черги поверх двох звичайних стеків
- ✓Правильна відповідь: Наступний більший елемент для кожного за O(n)
- 3Сортування масиву чисел за лінійний час O(n)
Пояснення
Стек тримає індекси зі спадними значеннями. Коли приходить більше значення, воно знімає менші: нове значення і є їхнім «наступним більшим». Кожен індекс кладуть і знімають один раз, тож прохід O(n).