Выбор ответа Middle Стек и монотонный стек спрашивают часто обновлено
Следующий больший элемент
Вопрос
Для каждого элемента найти ближайший справа больший. Какой подход и сложность?
Попробуйте сами
Выберите вариант, и откроется разбор.
Показать ответ и разбор
Коротко
Правильный ответ: Монотонно убывающий стек индексов, O(n). Идём слева направо и держим в стеке индексы элементов, для которых ответ ещё не найден; значения в стеке убывают.
Варианты ответа
- Монотонно убывающий стек индексов, O(n)правильный ответ
- Вложенный цикл, O(n²) и быстрее нельзя
- Сортировка с сохранением индексов, O(n log n)
- Max-куча по ещё не обработанным, O(n log n)
Разбор
Идём слева направо и держим в стеке индексы элементов, для которых ответ ещё не найден; значения в стеке убывают. Пришёл больший: снимаем со стека всех меньших, для них он и есть ответ. Каждый индекс кладётся и снимается один раз: O(n).
- Квадратичный перебор можно улучшить.
- Сортировка теряет понятие «справа».
- Куча даёт O(n log n) и не нужна.
Ответьте сами, а не прочитайте
В тренажёре вопрос попадёт в повторения и вернётся, когда начнёт забываться. Плюс билеты с зачётом: 20 вопросов, не больше 2 ошибок.