Монотонный стек: как найти ближайший больший элемент за O(n)

Задача, которая выглядит квадратичной

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

[2, 1, 2, 4, 3]  →  [4, 2, 4, -1, -1]

Первое, что приходит в голову, — для каждого элемента бежать вправо и искать. Это O(n²), и на массиве в 10⁵ элементов решение не пройдёт по времени.

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

Что такое монотонный стек

Это обычный стек, в котором мы поддерживаем инвариант: элементы в нём всегда идут по возрастанию (или всегда по убыванию). Перед тем как положить новый элемент, мы выталкиваем все, которые нарушают порядок.

Вся магия в одной мысли: если элемент вытолкнули — значит, мы только что нашли для него ответ. Тот элемент, который его вытолкнул, и есть ближайший больший справа.

Разберём на массиве [2, 1, 2, 4, 3]. В стеке будем хранить индексы.

i=0, num=2  стек пуст            → кладём 2.           стек: [2]
i=1, num=1  1 < 2, порядок цел   → кладём 1.           стек: [2, 1]
i=2, num=2  2 > 1 → выталкиваем 1, ответ для 1 это 2
            2 = 2, не больше     → кладём 2.           стек: [2, 2]
i=3, num=4  4 > 2 → выталкиваем, ответ для 2 это 4
            4 > 2 → выталкиваем, ответ для 2 это 4
                                 → кладём 4.           стек: [4]
i=4, num=3  3 < 4                → кладём 3.           стек: [4, 3]

Остались в стеке 4 и 3 — для них большего справа нет, ответ −1.

Базовый шаблон

function nextGreaterElements(nums) {
  const result = new Array(nums.length).fill(-1);
  const stack = []; // храним индексы, а не значения

  for (let i = 0; i < nums.length; i++) {
    // пока текущий элемент больше вершины — он и есть её ответ
    while (stack.length > 0 && nums[i] > nums[stack[stack.length - 1]]) {
      const index = stack.pop();
      result[index] = nums[i];
    }

    stack.push(i);
  }

  return result;
}

nextGreaterElements([2, 1, 2, 4, 3]); // [4, 2, 4, -1, -1]

На Python:

def next_greater_elements(nums: list[int]) -> list[int]:
    result = [-1] * len(nums)
    stack: list[int] = []

    for i, num in enumerate(nums):
        while stack and num > nums[stack[-1]]:
            result[stack.pop()] = num
        stack.append(i)

    return result

Почему храним индексы, а не значения. Значение подсказывает, что сравнивать, но не подсказывает, куда записать ответ. С индексом у нас есть и то, и другое: nums[i] для сравнения и i для записи. Это первое, на что смотрит интервьюер.

Почему это O(n), а не O(n²)

Внутри цикла есть while — и это сбивает с толку. Кажется, что в худшем случае получится квадрат.

Аргумент простой: каждый индекс попадает в стек ровно один раз и выталкивается максимум один раз. Значит, суммарное число операций push и pop за всю работу алгоритма не больше 2n. Внешний цикл — n итераций. Итого O(n).

Это называется амортизационным анализом, и его стоит проговорить вслух. Формулировка «внутренний цикл не зависит от n, потому что каждый элемент выталкивается лишь однажды» — ровно то, что хочет услышать интервьюер.

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

Четыре варианта одной техники

Меняя два знака, получаем четыре разные задачи. Это стоит запомнить как таблицу.

Отдельно есть вопрос про строгость сравнения. Если в массиве возможны равные элементы и по условию они «не считаются большими», используйте строгое >. Если равный элемент должен считаться ответом — нестрогое >=. Эту деталь полезно уточнить у интервьюера вслух: это показывает внимание к краевым случаям.

Прикладная задача: сколько ждать потепления

Классика с собеседований. Дан массив дневных температур, для каждого дня нужно сказать, через сколько дней станет теплее.

[73, 74, 75, 71, 69, 72, 76, 73]
 →  [1,  1,  4,  2,  1,  1,  0,  0]

Отличие от базового шаблона только одно: в ответ пишем не значение, а разницу индексов.

function dailyTemperatures(temperatures) {
  const result = new Array(temperatures.length).fill(0);
  const stack = [];

  for (let i = 0; i < temperatures.length; i++) {
    while (
      stack.length > 0 &&
      temperatures[i] > temperatures[stack[stack.length - 1]]
    ) {
      const prev = stack.pop();
      result[prev] = i - prev; // сколько дней прошло
    }

    stack.push(i);
  }

  return result;
}

Здесь особенно видно, зачем нужны индексы: без них посчитать i - prev было бы невозможно.

Задача посложнее: максимальная площадь в гистограмме

Дан массив высот столбиков, нужно найти площадь наибольшего прямоугольника, вписанного в гистограмму. Это уже уровень hard, и монотонный стек — канонический способ её решить.

Ключевая мысль: для каждого столбика прямоугольник максимальной площади с его высотой ограничен ближайшими меньшими элементами слева и справа. То есть нам нужны обе границы — и обе даёт монотонный стек.

function largestRectangleArea(heights) {
  const stack = [];
  let best = 0;

  // фиктивный ноль в конце вытолкнет всё, что осталось в стеке
  const extended = [...heights, 0];

  for (let i = 0; i < extended.length; i++) {
    while (
      stack.length > 0 &&
      extended[i] < extended[stack[stack.length - 1]]
    ) {
      const height = extended[stack.pop()];
      // левая граница — новая вершина стека, правая — текущий i
      const left = stack.length === 0 ? -1 : stack[stack.length - 1];
      const width = i - left - 1;
      best = Math.max(best, height * width);
    }

    stack.push(i);
  }

  return best;
}

largestRectangleArea([2, 1, 5, 6, 2, 3]); // 10

Приём с фиктивным нулём в конце — стандартный. Без него пришлось бы после основного цикла писать отдельный блок для «доработки» оставшегося стека, а это лишний код и лишний шанс ошибиться.

Типичные ошибки

Хранение значений вместо индексов. Работает только в самых простых задачах, во всём остальном приводит к тупику.

Забытая обработка остатка стека. После цикла в стеке лежат элементы, для которых ответа не нашлось. Если ответ по умолчанию не −1 и не 0, их нужно обработать явно — или добавить фиктивный элемент, как в гистограмме.

Путаница со строгим и нестрогим сравнением. На массивах без дубликатов оба варианта дают одинаковый результат, поэтому ошибка всплывает только на хитром тесте.

Попытка обойтись одним проходом там, где нужны обе границы. В задачах вроде гистограммы нужны и левая, и правая границы. Иногда проще сделать два прохода и получить два массива, чем выкручиваться в одном.

Как распознать задачу

Монотонный стек стоит доставать, когда в условии звучит:

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

Общий признак: для каждого элемента нужно найти его «соседа» по некоторому условию, и наивное решение выглядит как вложенный цикл.

Что запомнить

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

Закрепите на практике

Начните с задачи на корректность скобочной последовательности — она проще, но ставит базовое понимание стека. После неё шаблон монотонного стека ложится гораздо легче.

Пройди собеседование в топ-компанию

Платформа для подготовки

Решай алгоритмические задачи как профи

✓ Популярные алгоритмы✓ Разбор решений✓ AI помощь

Начать сейчас→