re:re:actable
Урок 062 минуты чтения

Что такое monotonic stack?

На этой странице
Кратко

Monotonic stack - стек, который поддерживает элементы в монотонном порядке. Он нужен для задач "следующий больший/меньший элемент", histogram, temperatures и удаления лишних элементов.

Вопрос

Что такое monotonic stack и какие задачи он решает за O(n)?

Идея

Стек хранит кандидатов в порядке:

increasing или decreasing

Когда приходит новый элемент, мы выталкиваем элементы, которые больше не могут быть ответом.

Next greater element

function nextGreater(nums: number[]): number[] {
  const result = new Array(nums.length).fill(-1)
  const stack: number[] = []
 
  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
}

В стеке лежат индексы элементов, для которых следующий больший еще не найден. Значения по этим индексам убывают от дна стека к вершине - отсюда название "монотонный". Пример nums = [2, 1, 3, 2, 4]:

inums[i]Кого выталкиваем (ответ = nums[i])stack после (значения)result
02никого[2][-1, -1, -1, -1, -1]
11никого, 1 < 2[2, 1]без изменений
231, затем 2[3][3, 3, -1, -1, -1]
32никого[3, 2]без изменений
442, затем 3[4][3, 3, 4, 4, -1]

Для 4 больший так и не нашелся - остался -1.

Каждый индекс попадает в стек и выходит из него не более одного раза.

Сложность:

Time: O(n)
Space: O(n)

Когда узнавать паттерн?

  • next greater;
  • next smaller;
  • previous greater;
  • daily temperatures;
  • largest rectangle in histogram;
  • remove duplicate letters;
  • "найти ближайший элемент слева/справа".

Что отвечать на собеседовании?

Monotonic stack хранит элементы в возрастающем или убывающем порядке. Когда новый элемент нарушает порядок, мы извлекаем элементы из стека и часто находим для них ответ. Хотя внутри есть while, каждый элемент добавляется и удаляется максимум один раз, поэтому сложность обычно O(n).

Что важно помнить: частые ошибки

  • Хранить значения, когда нужны индексы.
  • Не понимать, почему while не делает O(n^2).
  • Путать increasing и decreasing stack.
  • Забывать заполнить default answer.
  • Ошибаться в сравнении >/>=.

Мини-шпаргалка

  • Stack + порядок.
  • Часто храним индексы.
  • Каждый элемент push/pop один раз.
  • Time обычно O(n).
  • Next greater - классика.
  • Важно выбрать знак сравнения.

Документация

LeetCode: Monotonic Stack problems.

Дочитали до конца?
Отметьте урок — прогресс сохранится в браузере.

Поиск

Поиск по урокам