Монотонный стек

Монотонный стек: как это работает?

Стек хранит индексы, а не значения. Каждый индекс ждёт там своего ответа.

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

Направление сравнения решает результат. Снимайте, пока верхушка меньше, и получите следующий больший.

Разверните сравнение на «пока верхушка больше». Так получается следующий меньший.

Всё, что осталось в стеке, ответа не нашло. У этих позиций остаётся значение по умолчанию.

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

1. [0]Кладём индекс 0. Значение 2 лежит в стеке.
2. [0, 1]Значение 1 проигрывает двойке. Снимать нечего, кладём индекс 1.
3. [2]Значение 5 бьёт 1, затем 2. Оба снимаются с ответом 5.
4. [2, 3]Значение 3 проигрывает пятёрке. Кладём индекс 3.
5. [2, 3]Вход кончился. У индексов 2 и 3 остаётся -1.

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

Монотонный стек: разбор примера

Температура по дням

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

Если тёплого дня нет, ответ 0. Вложенные циклы дают O(n в квадрате) и не проходят по времени.

Это тот же следующий больший элемент, только нужна дистанция вместо значения.

Идём слева направо. Снимаем каждый день в стеке, который холоднее сегодняшнего.

Сегодня и есть его первый тёплый день. Ожидание равно разнице индексов.

Дни, оставшиеся в стеке, тепла не дождались. У них остаётся 0.

function dailyTemperatures(temps) {
    const wait = new Array(temps.length).fill(0);
    const stack = []; // indices, coldest at the bottom

    for (let today = 0; today < temps.length; today++) {
        while (
            stack.length &&
            temps[stack[stack.length - 1]] < temps[today]
        ) {
            const colder = stack.pop();
            wait[colder] = today - colder;
        }
        stack.push(today);
    }

    return wait; // days still on the stack keep their 0
}

Монотонный стек: когда применять?

Эти формулировки в условии ведут сюда:

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

Монотонный стек: с чем путают?

• Стек (Stack (LIFO)): Обычный стек снимает по вашей команде. Монотонный снимает по сравнению.
• Монотонный дек (Monotonic deque (sliding window max/min)): Дек ещё и выбрасывает элементы, выпавшие из окна. Если никто не устаревает, хватит стека.
• Скользящее окно (переменное) (Sliding window (variable)): Окно отвечает на вопросы про диапазон. Этот стек отвечает про один граничный элемент.
• Двоичная куча (Binary heap / priority queue): Куча даёт глобальный максимум за O(log n). Стек даёт ближайшего большего соседа за O(1).
• Сортировка с компаратором (Sort with a custom comparator): Сортировка выбрасывает позиции. Вопросы про следующий больший целиком про позиции.

Монотонный стек: частые ошибки

• Кладут значения вместо индексов

  Для расстояния нужна позиция. Кладите индекс, а значение берите как temps[i].

• Путают направление сравнения

  Меньше на верхушке даёт следующий больший. Больше на верхушке даёт следующий меньший.

• Забывают про остаток стека

  Элементы, оставшиеся в стеке, ответа не нашли. Решите заранее: -1, 0 или длина массива.

• Неверно обрабатывают равные значения

  Строгое < оставляет дубликаты в стеке, <= снимает их. Проверьте на [2, 2, 2].

Монотонный стек: задачи с собеседований

• Следующий больший элемент: Паттерн без маскировки. Остальные задачи переформулируют его.
• Температура по дням: Тот же следующий больший, но спрашивают дистанцию.
• Наибольший прямоугольник в гистограмме: Каждому столбцу нужен первый меньший сосед с обеих сторон.
• Сбор дождевой воды: Вода стоит между столбцом и следующим более высоким.
• Биржевой спан: Следующий больший в обратную сторону, со счётом дней.
• Удалить k цифр: Снимаем большие цифры, чтобы осталось наименьшее число.
• Сумма минимумов подмассивов: Каждое значение владеет отрезком между меньшими соседями.

Монотонный стек: сложность по времени и памяти

O(n)

n до 1e5 элементов даёт O(n). Каждый элемент кладут один раз и снимают не больше раза.