Паттерн: Монотонный стек

Признак в условии

• «следующий больший / меньший элемент»
• «сколько дней до более тёплого»
• «наибольший прямоугольник в гистограмме»
• элементы «съедают» друг друга по правилу

Идея

Стек хранит индексы, значения в нём монотонны. Пока новый элемент нарушает монотонность, снимаем вершину - для неё текущий элемент и есть ответ. Каждый индекс кладётся и снимается один раз, поэтому O(n) несмотря на while.

Шаблон

const res = new Array(nums.length).fill(0);
const stack = [];
for (let i = 0; i < nums.length; i++) {
  while (stack.length && nums[i] > nums[stack[stack.length - 1]]) {
    const j = stack.pop();
    res[j] = i - j;
  }
  stack.push(i);
}

Сложность

Время O(n), память O(n).

Частые ошибки

• в стеке хранятся значения, а потом нужен индекс
• строгое и нестрогое сравнение путают (влияет на обработку равных элементов)
• забывают, что оставшиеся в стеке индексы ответа не получили

Мнемоника

«Пока вершина хуже - она нашла свой ответ»

Не путать с

• Стек - признак монотонного - вопрос «следующий больший/меньший» или «какой участок этот элемент доминирует»
• Куча и top-K - куча даёт k лучших в произвольном порядке прихода; монотонный стек - ближайший по позиции, и он линейный

Задачи на этот паттерн

• следующий больший элемент
• столкновение астероидов
• сколько воды удержится

Признак в условии

• вложенность: скобки, теги, вложенные структуры
• «последний открытый», «отменить последнее»
• разбор выражений, распаковка строк

Идея

Кладём то, что ждёт закрытия; снимаем, когда закрытие пришло. Пустота стека в конце - обязательная часть проверки корректности.

Шаблон

const stack = [];
for (const c of s) {
  if (isOpen(c)) stack.push(c);
  else if (stack.pop() !== pairFor(c)) return false;
}
return stack.length === 0;

Сложность

Время O(n), память O(n).

Частые ошибки

• не проверена пустота стека в конце: строка ( пройдёт как корректная
• pop на пустом стеке даёт undefined - это надо учитывать в сравнении
• многозначные числа при разборе набираются по одной цифре

Мнемоника

«Открыл - положи, закрыл - сверь»

Не путать с

• Монотонный стек - обычный стек только помнит порядок (скобки, отмена); монотонный ещё и выталкивает элементы, находя каждому ответ
• Обход в глубину - обход в глубину - это тот же стек, только неявный, в рекурсии

Задачи на этот паттерн

• правильные скобки
• стек с минимумом
• обратная польская запись
• распаковка строки
• нормализация пути

Суть

Стек работает по правилу LIFO: последним пришёл, первым ушёл. В JS это обычный массив с push, pop и at(-1), все за O(1). Стек нужен, когда нужно «вернуться» к последнему незакрытому делу: скобка, вызов функции, операнд выражения.

Как распознать по условию

• вложенность: скобки, теги, пути a/b/../c;
• вычисление выражений, обратная польская запись;
• «ближайший больший / меньший слева или справа», «через сколько дней потеплеет»;
• «удали символы, чтобы получилось минимальное число», гистограммы;
• итеративный DFS вместо рекурсии.

Шаблон: скобки

function isValid(s) {
  const pair = { ')': '(', ']': '[', '}': '{' };
  const stack = [];
  for (const ch of s) {
    if (ch in pair) {
      if (stack.pop() !== pair[ch]) return false;
    } else {
      stack.push(ch);
    }
  }
  return stack.length === 0; // не забыть!
}

Шаблон: монотонный стек

Ближайший больший справа:

function nextGreater(a) {
  const res = new Array(a.length).fill(-1);
  const st = []; // индексы, значения убывают
  for (let i = 0; i < a.length; i++) {
    while (st.length && a[st.at(-1)] < a[i]) {
      res[st.pop()] = a[i];
    }
    st.push(i);
  }
  return res;
}

Как выбрать вид:

• ищем ближайший больший → стек убывающий (снимаем меньших);
• ищем ближайший меньший → стек возрастающий;
• нужен ответ слева → смотрим вершину стека перед push; справа → записываем ответ при pop.

Сложность

Каждый элемент кладётся и снимается один раз: O(n) времени, O(n) памяти, несмотря на вложенный while.

Стек с минимумом

Храним пары [value, minSoFar]: getMin это stack.at(-1)[1], всё O(1).

Ловушки

• Не проверить, что стек пуст в конце ("((").
• pop из пустого массива вернёт undefined: учитывать это в сравнении.
• Хранить значения, когда нужны расстояния (нужны индексы).
• Перепутать строгое и нестрогое сравнение при равных элементах.

Что спросят на собесе

• Проверь правильность скобочной последовательности.
• Найди ближайший больший элемент справа за O(n).
• Как сделать стек с минимумом за O(1)?
• Почему монотонный стек линейный, если внутри while?