Где применяется
1. Задача
Посмотри на строку кода с вложенными скобками: foo([a, {b: 1}]). Каждой ( нужна ), каждой [ нужна ], каждой { нужна }. И закрываться они обязаны в правильном порядке. Открыл квадратную, потом фигурную: фигурная должна закрыться раньше квадратной. Ошибёшься, и редактор сразу подчеркнёт это место.
Теперь сделай такую проверку сам, в коде, для всей строки. Сложность в порядке. В ([)] количество верное: две открывающие и две закрывающие. Но вложенность перепутана: ) пытается закрыться, пока [ ещё открыта. Это надо поймать.
Первая идея: считать. Прибавляй 1 на каждой открывающей скобке, отнимай 1 на каждой закрывающей и проверь, что в конце получился 0. На ([)] эта проверка ошибается: в конце 0, и строка признана верной. Счётчик знает, сколько скобок открыто, но не помнит, какие именно.
Этот шаг из платной части
Бесплатные шаги в начале курса (их 33) открыты всем: урок, задача и тесты. Этот шаг открывается с полным доступом. Начни с бесплатного аккаунта и бесплатных шагов.
Завести бесплатный аккаунтПосмотреть, что входитisValid("([]{()})")Проверяем, что каждая скобка закрыта в правильном порядке. Открывающая идёт в стек. Закрывающая должна совпасть с вершиной.
Как узнать
Эти слова в условии значат этот паттерн
- корректные скобки / сбалансированные скобки
- сопоставить самую недавнюю открывающую с ближайшей закрывающей
- отмена, откат к последнему состоянию, вложенная структура
- вычислить выражение с вложенными операторами
- обработать в порядке, обратном порядку поступления
Похоже, но не то
- Монотонный стек (Monotonic stack)
Там стек упорядочен, и каждое снятие отвечает на вопрос. Обычный стек помнит лишь то, что открыто.
- Рекурсия (Recursion)
Каждый рекурсивный вызов и так лежит на стеке. Свой стек снимает ограничение по глубине.
- Обход графа BFS / DFS (Graph BFS / DFS)
Очередь даёт обход в ширину, стек даёт обход в глубину. Тот же обход, другой контейнер.
- Монотонная дек-очередь (максимум/минимум окна) (Monotonic deque (sliding window max/min))
Дек читается и подрезается с обоих концов. Стек трогает только вершину.
Каждая вставка и снятие стоят O(1), значит n операций дают O(n). Память в худшем случае O(n).
На LeetCode
Задачи на скобки и вложенность, где последнее открытое закрывается первым. Каждую открывающую кладёшь в стек, а на закрывающей снимаешь и проверяешь пару.
Задача урока, только в строке нет ничего, кроме скобок.
Клади в стек индекс каждой открывающей, снимай на парной закрывающей и удали закрывающие без пары и открывающие, что остались в стеке.
На открывающей скобке клади в стек число повторов и уже собранный текст, а на закрывающей снимай их и повторяй.
Клади в стек индексы вместо символов, тогда расстояние до новой вершины после снятия даёт длину правильного куска.