Дни до потепления

Дни до потепления: Эффективное решение через стек

Понимание задачи

Нужно для каждого дня найти, сколько дней нужно ждать, пока придёт более тёплый день. Это классическая задача на Monotonic Stack (монотонный стек) — один из самых важных паттернов в алгоритмике.

Наивный подход O(n²) — неэффективно

def warm_days_naive(temps: list[int]) -> list[int]:
    """Перебираем каждый день, смотрим в будущее."""
    n = len(temps)
    result = [0] * n
    
    for i in range(n):
        for j in range(i + 1, n):
            if temps[j] > temps[i]:
                result[i] = j - i
                break
    
    return result

Проблема: Для 30000 дней (месяц) = 30000² / 2 = 450 млн операций. Слишком медленно.

Оптимальный подход: Monotonic Stack O(n)

Идея: идём с конца массива назад, держим в стеке индексы дней в порядке убывания температуры.

def warm_days(temps: list[int]) -> list[int]:
    """
    Находит дни до потепления за O(n) время, O(n) память.
    
    Args:
        temps: список температур [73, 74, 75, 71, 69, 72, 76, 73]
    
    Returns:
        Количество дней до потепления для каждого дня
    """
    n = len(temps)
    result = [0] * n
    stack = []  # Стек индексов в порядке убывания температур
    
    # Идём с конца массива к началу
    for i in range(n - 1, -1, -1):
        # Удаляем из стека дни с температурой <= текущего дня
        # (они никому уже не помогут, они холоднее текущего)
        while stack and temps[stack[-1]] <= temps[i]:
            stack.pop()
        
        # Если стек не пуст, верхний элемент — первый тёплый день
        if stack:
            result[i] = stack[-1] - i
        
        # Добавляем текущий день в стек
        stack.append(i)
    
    return result

Пример пошагово для [73, 74, 75, 71, 69, 72, 76, 73]:

Шаг 7 (i=7, temp=73):
  stack = [7]
  result[7] = 0

Шаг 6 (i=6, temp=76):
  stack = [7] — 73 <= 76, удаляем
  stack = []
  result[6] = 0
  stack = [6]

Шаг 5 (i=5, temp=72):
  stack = [6] — 76 > 72, не удаляем
  result[5] = 6 - 5 = 1
  stack = [6, 5]

Шаг 4 (i=4, temp=69):
  stack = [6, 5] — 72 > 69, не удаляем
  result[4] = 5 - 4 = 1
  stack = [6, 5, 4]

Шаг 3 (i=3, temp=71):
  stack = [6, 5, 4]
  Удаляем 4 (69 <= 71)
  stack = [6, 5] — 72 > 71, не удаляем
  result[3] = 5 - 3 = 2
  stack = [6, 5, 3]

Шаг 2 (i=2, temp=75):
  Удаляем 3 (71 <= 75)
  Удаляем 5 (72 <= 75)
  stack = [6] — 76 > 75, не удаляем
  result[2] = 6 - 2 = 4
  stack = [6, 2]

Шаг 1 (i=1, temp=74):
  stack = [6, 2] — 75 > 74, не удаляем
  result[1] = 2 - 1 = 1
  stack = [6, 2, 1]

Шаг 0 (i=0, temp=73):
  Удаляем 1 (74 > 73) — нет, 74 > 73
  result[0] = 1 - 0 = 1
  stack = [6, 2, 1, 0]

Результат: [1, 1, 4, 2, 1, 1, 0, 0] ✓

Сложность анализ

Временная сложность: O(n)

• Каждый элемент добавляется в стек один раз
• Каждый элемент удаляется из стека один раз
• Итого: 2n операций

Пространственная сложность: O(n)

• Стек может содержать до n элементов (для убывающего массива)

Альтернатива: Декрементирующая очередь (Deque)

Для случаев с повторяющимися температурами:

from collections import deque

def warm_days_deque(temps: list[int]) -> list[int]:
    """
    Если в массиве много одинаковых температур.
    """
    n = len(temps)
    result = [0] * n
    dq = deque()  # Хранит пары (temperature, index)
    
    for i in range(n - 1, -1, -1):
        # Удаляем дни с temp <= текущего
        while dq and dq[-1][0] <= temps[i]:
            dq.pop()
        
        if dq:
            result[i] = dq[-1][1] - i
        
        dq.append((temps[i], i))
    
    return result

Тесты для проверки

def test_warm_days():
    # Основной пример
    assert warm_days([73, 74, 75, 71, 69, 72, 76, 73]) == [1, 1, 4, 2, 1, 1, 0, 0]
    
    # Убывающий массив
    assert warm_days([89, 62, 70, 58, 47, 47, 46, 76, 100, 70]) == [8, 1, 5, 4, 3, 3, 1, 1, 0, 0]
    
    # Один элемент
    assert warm_days([30]) == [0]
    
    # Все одинаковые
    assert warm_days([70, 70, 70]) == [0, 0, 0]
    
    print("Все тесты пройдены!")

Ключевые выводы

1. Monotonic Stack — универсальный паттерн для задач:

   • "следующий больший элемент"
   • "дней до X"
   • "наибольший прямоугольник в гистограмме"

2. Инвариант: В стеке всегда элементы в убывающем (или неубывающем) порядке

3. Сложность: O(n) время, хотя выглядит как вложенные циклы

4. Практика: Это частая задача на собеседованиях, показывает понимание структур данных