Где применяется
1. Задача
У тебя есть температуры за 8 дней: [73, 74, 75, 71, 69, 72, 76, 73]. Для каждого дня надо узнать, сколько дней ждать, пока станет теплее. В первый день 73, во второй 74, значит ответ для первого дня 1. В третий день 75, и теплее становится только на седьмой день (76), значит ответ 4. Если более тёплого дня так и не будет, ответ 0.
Первый план: от каждого дня идти вперёд, пока не найдётся день теплее. Это работает и даёт верный ответ. Но на длинном ряду это цикл внутри цикла. На 10 000 дней выйдет почти 50 000 000 сравнений (49 995 000, если каждый день холоднее предыдущего). Один и тот же тёплый день будут заново просматривать все дни, которые ждут перед ним.
Можно ответить для всех дней сразу за один проход. Каждый день при этом обрабатывается ограниченное число раз, как бы ни шли температуры.
Этот шаг из платной части
Бесплатные шаги в начале курса (их 33) открыты всем: урок, задача и тесты. Этот шаг открывается с полным доступом. Начни с бесплатного аккаунта и бесплатных шагов.
Завести бесплатный аккаунтПосмотреть, что входитnextGreater([2, 7, 3, 1, 5, 4, 8])Для каждого числа ищем первое большее справа. В стеке лежат индексы, которые ещё ждут ответа.
Столбики: 40 замеров, которые постепенно снижаются, поэтому большее значение обычно далеко.
Одна операция: одно сравнение. За каждый кадр все дорожки делают одинаковое число операций, поэтому медленная отстаёт.
O(n²)O(n)
Операции для n чисел и примерное время при 100 миллионах простых операций в секунду. Это оценка по тому же счёту, а не замер.
Как узнать
Эти слова в условии значат этот паттерн
- ближайший больший / ближайший меньший элемент
- сколько дней ждать потепления
- наибольший прямоугольник в гистограмме
- сколько воды соберётся между столбиками
- отрезок/серия, заканчивающаяся первым большим или меньшим значением
Похоже, но не то
- Стек (Stack (LIFO))
Обычный стек снимает по вашей команде. Монотонный снимает по сравнению.
- Монотонный дек (Monotonic deque (sliding window max/min))
Дек ещё и выбрасывает элементы, выпавшие из окна. Если никто не устаревает, хватит стека.
- Скользящее окно (переменное) (Sliding window (variable))
Окно отвечает на вопросы про диапазон. Этот стек отвечает про один граничный элемент.
- Двоичная куча (Binary heap / priority queue)
Куча даёт глобальный максимум за O(log n). Стек даёт ближайшего большего соседа за O(1).
- Сортировка с компаратором (Sort with a custom comparator)
Сортировка выбрасывает позиции. Вопросы про следующий больший целиком про позиции.
n до 1e5 элементов даёт O(n). Каждый элемент кладут один раз и снимают не больше раза.
На LeetCode
Задачи, где для каждого элемента нужен следующий или предыдущий больший или меньший. Монотонный стек из позиций, которые ещё ждут ответа, отвечает каждой из них один раз.
Сделай проход из урока по nums2, сложи ответы в словарь и прочитай их для nums1.
Пример из начала урока, только ответ равен расстоянию между позициями, а не значению.
Тот же стек, только смотрит назад: каждая цена снимает со стека все цены не выше себя и забирает себе их отрезки.
Когда столбик снимают, тот, кто его снял, и новая вершина стека оказываются ближайшими более низкими соседями с двух сторон и задают ширину прямоугольника.