Самое сильное за месяц
Сейсмологическая служба ведёт ленту событий: новые землетрясения встают в конец, а те, что стали старше месяца, уходят из начала. Дежурному в любой момент нужно знать самое сильное из тех, что сейчас в ленте. Лента — это очередь, и к обычным операциям очереди добавляется вопрос «какой максимум?».
Один из тестов — настоящий каталог USGS: все землетрясения магнитудой 5 и больше за 2015–2025 годы по порядку; после каждого из ленты уходят события старше 30 дней, а затем дежурный спрашивает максимум. Магнитуды умножены на 100.
Вход
В первой строке число операций q (1 ≤ q ≤ 300 000). Дальше по одной операции в строке:
+ x— поставить число x в конец очереди (0 ≤ x ≤ 10⁹);-— убрать число из начала очереди (очередь не пуста);?— спросить наибольшее число в очереди (очередь не пуста).
Выход
На каждый вопрос ? — наибольшее число, которое в этот момент есть в очереди, по одному в строке.
Примеры
Пример 1
9 + 5 + 3 ? + 7 ? - ? - ?
5 7 7 7
Пример 2
11 + 9 + 1 + 8 + 2 ? - ? - ? - ?
9 8 8 2
Ограничения
- Время · Python
- 4000 мс
- Время · Go
- 1500 мс
- Память
- 256 МБ
- Проверка
- 7 тестов
Разбор
Открывайте по ступеням: каждая следующая подсказывает больше. Можно сразу к решению — но задача, решённая с одной подсказкой, запоминается лучше.
1Подсказка 1
Перебирать всю очередь на каждый вопрос — O(n) на вопрос. Четвёртый тест: сто тысяч чисел в очереди и сто тысяч вопросов. А для стека максимум узнать легко: пусть каждая запись помнит максимум всех записей под ней. Почему со стеком это работает, а с очередью нет?
2Подсказка 2
У стека всё меняется с одного конца, и «максимум под собой» у записи никогда не устаревает. А что если собрать очередь из двух стеков?
3Идея
Очередь на двух стеках. Новые числа кладём во «входной» стек. Брать из начала будем из «выходного»; когда он пуст, переливаем в него входной целиком: при переливании порядок переворачивается, и самое старое число оказывается сверху. Каждая запись в обоих стеках хранит пару «число, максимум от дна стека до этой записи». Тогда максимум всей очереди — больший из максимумов на вершинах двух стеков.
4Разбор
Три операции. + x: положить во входной стек пару (x, max(x, максимум на его вершине)). -: если выходной стек пуст, перелить в него входной, пересчитывая максимумы уже для выходного стека; затем снять вершину выходного. ?: сравнить максимумы на вершинах — тех стеков, что не пусты.
Переливание выглядит дорогим, но каждое число переливается ровно один раз за свою жизнь: попало во входной стек, однажды переехало в выходной, потом ушло. Поэтому на все q операций уходит O(q) действий — каждая операция стоит O(1) амортизированно, тем же счётом, что и append у динамического массива.
Есть и другое решение — монотонная очередь: двусторонняя очередь, в которой хранятся только числа, у которых ещё есть шанс стать максимумом, по убыванию. Оно тоже линейное, о нём — в статье о монотонном стеке.
На настоящем каталоге ответы читаются как хроника. Самые сильные события в нём — магнитуда 8,3 у Ильяпеля в Чили в сентябре 2015 года и 8,8 у Камчатки в июле 2025-го: после каждого из них ответ на «?» 30 дней держится на 830 и на 880.
4+Решение
5Сложность
O(q) на все операции, O(1) амортизированно на каждую. Память — O(n) на числа в очереди.
6Типичные ошибки
- Перебор очереди на каждый вопрос. Верно, но квадратично на четвёртом тесте.
- Один общий максимум. Хранить одно число «текущий максимум» нельзя: когда максимум уходит из начала, неизвестно, кто следующий (второй пример).
- Переливать при каждом «-». Переливать нужно, только когда выходной стек пуст. Иначе порядок перепутается, а время станет квадратичным.
- Куча с ленивым удалением работает, но за O(log n) на операцию и требует помнить, какие числа уже ушли.