Алгоритмы с нуля
Списки, стеки, очереди: собери тулкит последовательностей
Читать про движения pointer — не то же самое, что делать их самому не теряя узла. Собери маленькую библиотеку, которая держит последовательность тремя способами — list, stack, queue — добавь deque и решатель на monotonic stack и докажи каждую заявку о сложности своими измерениями.
Преврати ментальную модель юнита в работающий код: реализуй каждую структуру из примитивов (без встроенных stack/queue/deque), защити сложность каждой операции тестом и примени monotonic stack к реальной задаче next-greater от начала до конца.
Собери 'тулкит последовательностей' на языке по выбору: singly linked list с sentinel-головой, stack и queue, deque с O(1) на обоих концах и решатель на monotonic stack — каждое реализовано с нуля, каждое подкреплено тестом, демонстрирующим корректность и заявленную временную сложность.
- Все структуры реализованы из примитивов — внутри не используются предоставленные языком классы Stack/Queue/Deque/LinkedList.
- Проходящий набор тестов: разворот зеркалит список из 1000 узлов, hasCycle корректен на цикличных и ацикличных входах, isBalanced обрабатывает вложенные и несовпадающие скобки, BFS печатает узлы по уровням, а nextGreaterElement совпадает с эталоном-перебором на всех случайных кейсах.
- Лог сложности показывает реальные тайминги: стоимость на операцию у queue на shift растёт с N (квадрат в сумме), а у queue на pointer/circular buffer остаётся плоской (линейно в сумме) — измерено, а не заявлено.
- Текст на один абзац: для каждой структуры назови операцию, задающую её стоимость (вставка в голову для list, dequeue для queue, push-once/pop-once для monotonic stack), и почему твоя реализация попадает в целевую сложность.
- Добавь findCycleStart через трюк второго прохода tortoise-and-hare (один pointer на head, другой на точке встречи, оба на скорости один) и протестируй на списках с циклами, стартующими в разных позициях.
- Обобщи решатель на monotonic stack в одну функцию, считающую next-greater, next-smaller, previous-greater и previous-smaller параметризацией сравнения и направления скана.
- Реши 'largest rectangle in histogram' на monotonic stack и сверь с перебором-эталоном O(n^2) на случайных высотах столбцов.
- Реализуй min-stack: stack, который также возвращает текущий минимум за O(1), используя вспомогательный stack — и объясни, почему один счётчик так не может.
Это цикл, который ты гоняешь на каждой реальной задаче с последовательностями: выбери структуру по доминирующей операции, реализуй из примитивов, чтобы реально делать движения pointer, и докажи сложность измерением, а не заявлением. Sentinel стирает спецслучаи головы; сохранение pointer на преемника держит разворот честным; pointer head/tail или circular buffer держат queue на O(1); а инвариант push-once/pop-once держит monotonic stack линейным. Собери тулкит один раз — и это станет мышечной памятью на интервью и в продакшене.