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

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

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

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

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

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

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

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

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

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

Источники: Wikipedia (англ.): All nearest smaller values

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;
}

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

def next_greater(nums):
    result = [-1] * len(nums)
    stack = []
    for i, x in enumerate(nums):
        while stack and nums[stack[-1]] < x:
            result[stack.pop()] = x
        stack.append(i)
    return result

function nextGreater(array $nums): array {
    $result = array_fill(0, count($nums), -1);
    $stack = [];
    foreach ($nums as $i => $x) {
        while ($stack && $nums[end($stack)] < $x) {
            $result[array_pop($stack)] = $x;
        }
        $stack[] = $i;
    }
    return $result;
}

    public static int[] nextGreater(int[] nums) {
        int[] result = new int[nums.length];
        Arrays.fill(result, -1);
        Deque<Integer> stack = new ArrayDeque<>();
        for (int i = 0; i < nums.length; i++) {
            while (!stack.isEmpty() && nums[stack.peek()] < nums[i]) {
                result[stack.pop()] = nums[i];
            }
            stack.push(i);
        }
        return result;
    }

    public static int[] NextGreater(int[] nums) {
        var result = new int[nums.Length];
        Array.Fill(result, -1);
        var stack = new Stack<int>();
        for (int i = 0; i < nums.Length; i++) {
            while (stack.Count > 0 && nums[stack.Peek()] < 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, warmest 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
}

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

Паттерн «Монотонный стек» нужен, когда в условии есть слова «ближайший больший / ближайший меньший элемент», «сколько дней ждать потепления» или «наибольший прямоугольник в гистограмме». Решение на нём обычно укладывается в O(n).

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

Слова в условии для всех паттернов собраны в одной таблице: шпаргалка по паттернам алгоритмов.

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

Паттерн «Монотонный стек» чаще всего путают с этими паттернами: Стек, Монотонный дек, Скользящее окно (переменное), Двоичная куча и Сортировка с компаратором.

• Стек (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 цифр и Сумма минимумов подмассивов.

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

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

У паттерна «Монотонный стек» целевая сложность O(n).

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