Введение в монотонный стек

Стек — это в основном ограничительный массив, который использует свойство LIFO . Мы используем поп() и нажать() Операции по удалению и вставке элементов в стек соответственно.

Задачи на основе стека считаются очень простыми, но монотонные стеки обычно используются для решения задач среднего и сложного уровня.

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

Давайте разберемся с термином монотонные стеки, разбив его на части.

Монотонный = это слово для математических функций. Функция y = f(x) монотонно возрастает или убывает, если она соответствует следующим условиям:

• Когда x увеличивается, y также всегда увеличивается, тогда это монотонно возрастающая функция.
• Когда x увеличивается, y всегда уменьшается, тогда это монотонно убывающая функция.

См. приведенные ниже примеры:

• y = 2x +5, это монотонно возрастающая функция.
• y = -(2 ^x ), это монотонно убывающая функция.

Similarly, A stack is called a monotonic stack if all the elements starting from the bottom of the stack is either in increasing or in decreasing order.

Типы монотонного стека:

Существует 2 типа монотонных стеков:

• Монотонно увеличивающийся стек
• Монотонно убывающий стек

Монотонно увеличивающийся стек:

It is a stack in which the elements are in increasing order from the bottom to the top of the stack. 

Пример: 1, 3, 10, 15, 17

Как мы этого достигаем?

Если мы извлекаем из стека более крупные элементы перед помещением нового элемента, стек увеличивается снизу вверх.

Шаги для реализации:

• As we need monotonically increasing stack, we should not have a smaller element at top of a bigger element.
• So Iterate the given list of elements one by one :
  • Before pushing into the stack, POP all the elements till either of one condition fails:
    • Stack is not empty
    • Stack’s top is bigger than the element to be inserted.
  • Then push the element into the stack.

Посмотрите на иллюстрацию ниже, чтобы понять идею:

Иллюстрация:

Consider an array Arr[] = {1, 4, 5, 3, 12, 10}
For i = 0: stk = {1}
For i = 1: stk = {1, 4}
For i = 2: stk = {1, 4, 5}
For i = 3: stk = {1, 3}  [pop 4 and 5 as 4 > 3 and 5 > 3]
For i = 4: stk = {1, 3, 12}
For i = 5: stk = {1, 3, 10} [pop 12 as 12 > 10] 

Ниже приведен код для вышеуказанного подхода:

Временная сложность: O(N)
Вспомогательное пространство: O(N)

Монотонный убывающий стек:

A stack is monotonically decreasing if It’s elements are in decreasing order from the bottom to the top of the stack. 

Пример: 17, 14, 10, 5, 1

Как мы этого достигаем?

Если мы извлекаем меньшие элементы из стека перед тем, как поместить новый элемент, стек будет уменьшаться снизу вверх.

Шаги для реализации:

• As we need monotonically decreasing stack, we should not have a bigger element at top of a smaller element.
• So Iterate the elements of the list one by one:
  • Before pushing into the stack, POP all the elements till either of one condition fails:
    • Stack is not empty
    • Stack’s top is smaller than the element to be Inserted.
  • Then push the element into the stack.

См. иллюстрацию ниже для лучшего понимания:

Иллюстрация:

Consider an array: arr[] = {15, 17, 12, 13, 14, 10}
For i = 0: stk = {15}
For i = 1: stk = {17} [pop 15 as 15 < 17]
For i = 2: stk = {17, 12}
For i = 3: stk = {17, 13}  [pop 12 as 12 < 13]
For i = 4: stk = {17, 14}  [pop 13 as 13 < 14]
For i = 5: stk = {17, 14, 10}

Ниже приведена реализация вышеуказанного подхода:

Временная сложность: O(N)
Вспомогательное пространство: O(N)

Применение монотонного стека:

• Монотонный стек обычно используется для решения типичной проблемы, такой как следующий больший элемент. NGE (найдите первое значение справа, которое больше элемента.
• Также может использоваться для его сортов.
  • Следующий меньший элемент
  • Предыдущий больший элемент
  • Предыдущий меньший элемент
• Кроме того, мы используем его для получения наибольшего или наименьшего массива или строки по заданным условиям (оставшийся размер k/нет дубликатов).

Преимущества монотонного стека:

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

Недостатки монотонного стека:

• Это увеличивает пространственную сложность алгоритма в O(N) раз, т.е. на линейную сложность.
• Часто с этим сложнее справиться, так как теперь с существующей проблемой нам также нужно аккуратно обращаться со стеком. Поскольку после извлечения элементов из стека мы не можем их вернуть.

Статьи по Теме:

• Введение в стек — учебные пособия по структуре данных и алгоритмам
• Следующий больший элемент (NGE) для каждого элемента в заданном массиве