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

O(n)

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

Сигналы

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

Шаблон

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

Похоже, но не то

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

n до 1e5 элементов -> O(n): каждый элемент кладётся один раз и снимается не более одного раза, хотя внешне похоже на вложенный цикл.

Изучить этот паттерн