Выбор ответа Middle Стек и монотонный стек обновлено
Сколько дней до потепления
Вопрос
Задача: для каждого дня найти, через сколько дней станет теплее. Что хранить в стеке?
Попробуйте сами
Выберите вариант, и откроется разбор.
Показать ответ и разбор
Коротко
Правильный ответ: Индексы дней, температуры которых убывают от дна к вершине. Нужно расстояние, поэтому храним индексы.
Варианты ответа
- Сами температуры дней в порядке их поступления
- Разницу температур между текущим и прошлым днём
- Индексы дней, температуры которых возрастают от дна к вершине
- Индексы дней, температуры которых убывают от дна к вершинеправильный ответ
Разбор
Нужно расстояние, поэтому храним индексы. Когда приходит более тёплый день i, снимаем все индексы j с меньшей температурой и пишем res[j] = i - j. Стек остаётся убывающим по температуре. O(n).
- По одним температурам не вычислить расстояние.
- Разница температур не нужна в ответе.
- Возрастающий стек отвечает на «ближайший меньший», а не больший.
Ответьте сами, а не прочитайте
В тренажёре вопрос попадёт в повторения и вернётся, когда начнёт забываться. Плюс билеты с зачётом: 20 вопросов, не больше 2 ошибок.