Monotonic Stack and Deque

Задача звучит безобидно: для каждого дня узнать, через сколько дней метрика впервые станет больше. Наивно — от каждого дня идти вперёд до первого большего значения. На убывающем ряде это $O(n^2)$: миллион точек превращается в $10^{12}$ операций.

В ту же форму укладываются максимальный прямоугольник в гистограмме, сбор дождевой воды и «максимум внутри скользящего окна»: для каждой позиции ищется ближайший подходящий сосед, и перебор соседей даёт квадрат.

Стек при этом сам собой оказывается монотонным: всё, что нарушало бы порядок, из него уже снято. Отсюда и название, и линейное время.

день:      0    1    2    3    4    5
темп:     73   74   75   71   69   72

день 0:   стек [73]
день 1:   74 > 73  ->  ответ дня 0 = день 1      стек [74]
день 2:   75 > 74  ->  ответ дня 1 = день 2      стек [75]
день 3:   71 < 75                                стек [75, 71]
день 4:   69 < 71                                стек [75, 71, 69]
день 5:   72 > 69  ->  ответ дня 4 = день 5
          72 > 71  ->  ответ дня 3 = день 5
          72 < 75                                стек [75, 72]

у дней 2 и 5 ответа нет -- стек остался непустым

День 5 закрыл сразу два вопроса — за один свой шаг. Именно поэтому вложенный while внутри цикла не превращает решение в квадратичное: снимать можно только то, что раньше положили.

answer = [-1] * len(a)
stack = []                       # индексы, значения по ним убывают

for i, x in enumerate(a):
    while stack and a[stack[-1]] < x:
        j = stack.pop()          # для j нашёлся ближайший больший
        answer[j] = i
    stack.append(i)

return answer                    # -1 там, где большего справа нет

from collections import deque

dq = deque()                     # индексы, значения по ним убывают
for i, x in enumerate(a):
    while dq and a[dq[-1]] <= x:
        dq.pop()                 # этот уже никогда не станет максимумом
    dq.append(i)

    if dq[0] <= i - k:
        dq.popleft()             # вышел за левую границу окна

    if i >= k - 1:
        yield a[dq[0]]           # максимум текущего окна

• Инвариант — значения по индексам в стеке (деке) монотонны; всё, что нарушало бы порядок, уже снято.
• Время — $O(n)$: каждый индекс попадает в структуру один раз и снимается не более одного раза.
• Память — $O(n)$ в худшем случае (монотонный вход), $O(k)$ у дека в окне.

Ключевое наблюдение: если пришёл элемент $x$, а в стеке лежит меньший $y$, то $y$ больше никому не пригодится. Любой будущий элемент, для которого $y$ мог бы быть ответом, стоит правее $x$, а значит $x$ окажется к нему ближе и не меньше по величине. Выбрасывать $y$ безопасно навсегда, а не только на этом шаге.

Отсюда же линейность, и она амортизированная: внутренний while в сумме по всем итерациям выполняет не больше $n$ снятий, потому что каждое снятие соответствует одному добавлению. Считать сложность по виду кода («цикл в цикле — значит квадрат») здесь неверно, и это стоит проговорить вслух на собеседовании.

• Гистограмма — для каждого столбца ищутся ближайшие меньшие слева и справа: это границы прямоугольника, в котором он минимален.
• Прямоугольник из единиц в матрице — та же гистограмма, построчно накопленная.
• Сбор дождевой воды — второе классическое решение, по уровням, вместо двух встречных указателей.
• Удаление k цифр — снимаем со стека всё, что больше пришедшей цифры, пока лимит удалений не исчерпан.
• Монотонный дек — та же идея с доступом с двух концов: слева уходит вышедшее из окна, справа — бесперспективное.

• Хранить значения вместо индексов. Почти во всех задачах нужен ответ «через сколько шагов» или границы отрезка — без индексов их не восстановить.
• Строгое и нестрогое сравнение. < и <= различаются на дубликатах: одно даёт первый из равных, другое последний. Для гистограммы это влияет на двойной подсчёт площади.
• Незакрытый остаток. После цикла в стеке лежат элементы, для которых ответа нет; их нужно обработать явно — или заранее добавить в конец фиктивный бесконечный элемент.
• Дек не чистится слева. Максимум в окне вернёт устаревшее значение, если забыть снимать индексы, вышедшие за левую границу.
• Худший случай по памяти. На монотонном входе в стеке окажется весь массив: $O(n)$ памяти — это нормально, но об этом стоит сказать заранее.

1. Почему вложенный while не делает решение квадратичным?
2. Что лежит в стеке: значения или индексы — и почему это не вопрос вкуса?
3. Ближайший меньший слева: какой порядок в стеке и в какую сторону идти?
4. Максимальный прямоугольник в гистограмме [2, 1, 5, 6, 2, 3] — разберите руками.
5. Максимум в окне: по каким двум причинам индекс уходит из дека?