Стек (LIFO)

O(n)

Клади каждый элемент в стек по мере встречи; когда что-то должно совпасть с последним непарным партнёром, сними верхний элемент и сравни. То, что положено последним, всегда проверяется первым (last in, first out).

Сигналы

корректные скобки / сбалансированные скобкисопоставить самую недавнюю открывающую с ближайшей закрывающейотмена, откат к последнему состоянию, вложенная структуравычислить выражение с вложенными операторамиобработать в порядке, обратном порядку поступления

Шаблон

function isValid(s) {
    const stack = [];
    const pairs = { ')': '(', ']': '[', '}': '{' };
    for (const ch of s) {
        if (ch in pairs) {
            if (stack.pop() !== pairs[ch]) return false;
        } else {
            stack.push(ch);
        }
    }
    return stack.length === 0;
}

Похоже, но не то

Монотонный стек: Обычному стеку нужно лишь сопоставлять открывающие/закрывающие в порядке поступления, снимая верхний элемент при прямом совпадении. Монотонный стек решает другую задачу: он держит элементы отсортированными, снимая их, чтобы найти для каждого элемента ближайший больший или меньший сосед.

n до 1e5 символов/токенов -> O(n): каждый элемент кладётся один раз и снимается не более одного раза.

Изучить этот паттерн