Что такое монотонный стек и как решить задачу «следующий больший элемент»?

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

Следующий больший элемент

Для каждого a[i] нужен первый справа элемент больше него, иначе −1.

function nextGreater(a) {
  const res = new Array(a.length).fill(-1);
  const stack = []; // индексы, значения по ним убывают
  a.forEach((x, i) => {
    while (stack.length && a[stack.at(-1)] < x) {
      res[stack.pop()] = x;
    }
    stack.push(i);
  });
  return res;
}

// nextGreater([2, 1, 5, 3]) -> [5, 5, -1, -1]

Сложность

• Каждый индекс один раз кладётся и не более одного раза снимается — O(n) времени, хотя внутри цикла есть while.
• Память O(n) в худшем случае — на строго убывающем входе.
• Храните индексы, а не значения: так можно считать и расстояние до ответа (задача «тёплые дни»).

Вариации

• Кольцевой массив — пройти индексы от 0 до 2n−1, беря i % n.
• «Предыдущий меньший» — идти слева направо, стек возрастает.
• Наибольший прямоугольник в гистограмме, «ловушка для дождевой воды», stock span.

Коротко для собеседования

Монотонный стек за один проход находит для каждого элемента ближайшего большего или меньшего соседа: элемент снимается со стека ровно в тот момент, когда пришёл его ответ. Узнать такую задачу можно по наивному решению O(n²) с вложенным поиском ближайшего — стек превращает его в O(n).