Daily Temperatures

Средняя№739

Дана температура за каждый день подряд. Для каждого дня нужно сказать, сколько дней ждать, пока станет строго теплее; если теплее так и не станет, ответ 0. Наш пример: [64, 61, 61, 59, 66, 62, 63] даёт [4, 3, 2, 1, 0, 1, 0].

739 Daily TemperaturesРазбор · 1×

Пример: [64, 61, 61, 59, 66, 62, 63]: для каждого дня — сколько ждать потепления. Под температурами — ожидания; в стеке дни, которые ещё ждут, температуры к верху не растут.

064161261359466562663tempswait0000000stack—
ещё не дошлисегодняждёт в стекепроверяемый верхтёплый день найден

Все ожидания пока 0: это ответ для дня, после которого теплее не будет

01/39
сначала · назад · пуск · шаг
Скорость
1function dailyTemperatures(temps):
2 wait = list of len(temps) zeros
3 stack = empty stack // days still waiting
4 for day from 0 to len(temps) - 1:
5 while stack not empty and day is warmer than top:
6 prev = pop from stack
7 wait[prev] = day - prev
8 push day onto stack
9 return wait
состояние
wait
[0, 0, 0, 0, 0, 0, 0]
stack
–
day
–
prev
–
историянажмите шаг, чтобы вернуться

← → шаг · пробел — пауза

Почему это работает

  1. День ждёт в стеке, пока не придёт первый день теплее. Тот снимает его сразу, поэтому расстояние между ними и есть ожидание.
  2. Каждый день в стеке не теплее того, что под ним: более тёплый снял бы его. Поэтому если сегодня не теплее верха, то и всех ниже не теплее, и цикл можно остановить.
  3. Равная температура не снимает: нужен строго более тёплый день. Дни, оставшиеся в стеке в конце, его не дождались, и у них остаётся 0.

Сложность

Время O(n): каждый день кладётся в стек один раз и снимается не больше одного раза, поэтому внутренний цикл за всё время делает не больше n шагов. Память O(n) на стек и ответ.

дальшеТеперь реши её сам, без подсказок.

Решить на LeetCode ↗

Задача и её условие принадлежат LeetCode. Здесь — наш пересказ, наш пример и наше решение. Patterns Hero не связан с LeetCode.