Монотонный стек

Сегодня в Алматы +25°. Через сколько дней будет теплее? Чаще всего — завтра или послезавтра. Но если сегодня рекордная жара, ждать можно годами. По данным реанализа, после 1 августа 1946 года (+30,9° в среднем за сутки) более тёплый день в Алматы наступил только 9 июля 2021-го — через 75 лет. Наведите на любой день из 85 лет: стрелка покажет следующий более тёплый день.

Ответы для всех 31 046 дней посчитаны одним проходом. Если для каждого дня просматривать будущее до первого более тёплого, на рекордных днях пришлось бы пробегать десятки тысяч дней вперёд. Вместо этого программа держит стек дней, которые ещё ждут.

Идея

Идём по дням слева направо и держим в стеке те, для которых ещё не нашёлся более тёплый день. Их температуры не возрастают снизу вверх: если бы более поздний ждущий день был теплее раннего, ранний уже дождался бы. Новый день снимает с вершины всех, кто холоднее его, — для каждого из них он и есть ответ, — и сам ложится наверх. Такой стек, где значения всё время упорядочены, называют монотонным.

Внутри цикла по дням есть ещё один цикл снятия со стека, и кажется, что это квадрат. Но каждый день кладётся в стек один раз и снимается не больше одного раза, поэтому снятий за весь проход не больше n: время O(n) амортизированно. Дни, которые остались в стеке в конце, так и не дождались более тёплого — в ряду Алматы их 28, и первый из них — 9 августа 1944 года, самый тёплый день всех 85 лет.

Тот же стек отвечает и на обратный вопрос: сколько дней назад было так же тепло. Проход тот же, только ответ берётся с вершины после снятий. Так получается «самый тёплый день за столько-то лет»: 14 июля 2023 года (+31,3°) — самый тёплый за 28 828 дней, с 1944 года.

Наибольший прямоугольник

Вторая классическая задача монотонного стека — наибольший прямоугольник под гистограммой. Столбики стоят вплотную; какой самый большой прямоугольник можно вписать под ними? Для каждого столбика нужно знать, докуда влево и вправо идут столбики не ниже его, — то есть ближайший меньший с каждой стороны. Это та же задача о ближайшем, только меньшем, и решает её тот же стек: столбик снимается, когда пришёл более низкий, и в этот момент известны обе его границы.

А теперь настоящее применение. Где на фотографии поставить подпись, чтобы она не легла на детали? Разметим пиксели: спокойный, если яркость вокруг почти не меняется. Нужен наибольший прямоугольник из спокойных пикселей. Для каждой строки снимка посчитаем, сколько спокойных пикселей стоит столбиком над каждой точкой, — получится гистограмма, и прямоугольник с нижней стороной в этой строке — прямоугольник под ней.

Подвигайте порог. При маленьком спокойных пикселей мало, и подписи остаётся узкая полоска. При пороге около восьми находится гладкое небо над горами. Каждая строка стоит один проход стека, весь снимок — O(h·w).

Код

Ожидание более тёплого дня и «самый тёплый за столько-то дней» на всём ряду:

Место для подписи: спокойные пиксели, гистограмма по строкам и наибольший прямоугольник стеком. Снимок здесь уменьшен до 300 пикселей заранее, поэтому прямоугольник немного отличается от того, что находит сцена.

Монотонная очередь

Если ждущих разрешить снимать ещё и снизу, получится монотонная очередь. Она отвечает на вопрос «какой максимум в окне из последних w элементов» за O(1) на сдвиг: в очереди лежат только те, кто ещё может стать максимумом, по убыванию. Новый элемент выбрасывает с хвоста всех, кто меньше его, — им максимумом уже не стать, — а голова уходит, когда выпадает из окна. Это вторая половина скользящего окна: сумма окна правится прибавлением и вычитанием, а максимум — монотонной очередью.

Сколько это стоит

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

Важная мелочь — строгость сравнения. «Следующий строго теплее» и «следующий не холоднее» дают разные ответы на днях с одинаковой температурой, а в задаче о прямоугольнике от того, снимаются ли равные столбики, зависит, не посчитается ли площадь дважды или не потеряется. Решите это явно и проверьте на ряде из одинаковых чисел.

Задачи

Первая — ожидание тёплого дня, с тестом на всех 85 годах Алматы. Вторая — место для подписи на четырёх фотографиях автора сайта.