Всем привет, мы все знаем СТЕК, но Что такое монотонный стек?
Monotonic Stack is a special variation of the typical data structure Stack and appeared in many interview questions. As its name shows, monotonic stack contains all features that a normal stack has and its elements are all monotonic decreasing or increasing. It just uses some ingenious logic to keep the elements in the stack orderly (monotone increasing or monotone decreasing) after each new element putting into the stack.
Название проблемы в Leetcode: Следующий больший элемент I
Следующий больший элемент некоторого элемента x в массиве — это первый больший элемент, который находится справа от x в том же массиве.
Ограничения. Все целые числа в массиве являются положительными и уникальными.
Возьмем пример:
Given Array, arr : [7,2,1,6,9,5,4]
Допустим, длина массива равна L, здесь L = 7.
Мы должны найти следующий больший элемент каждого элемента массива. Если для данного элемента нет следующего большего элемента, то вернуть -1 для этого элемента.
Во-первых, создайте пустой стек размером L, скажем, S1={}.
Поместите первый элемент массива в стек S1, S1 = {7}
Теперь, когда мы начинаем вставлять другие элементы массива массив в стеке, мы должны иметь в виду, что вставляемый элемент должен быть меньше, чем верхний элемент стека, если он больше, то извлекайте из стека все элементы, которые меньше, чем вставляемый элемент, и сопоставьте их с вставляемым элементом как их следующий больший элемент.
Таким образом, мы получим сопоставление каждого элемента массива с его следующим большим элементом и элементами, которые остаются в стеке S1, чтобы не было следующего большего элемента, поэтому мы возвращаем -1 для этих элементов.
Временная сложность: O(N)Пространственная сложность:
O(N)
Другие варианты этой задачи:
1. Следующий меньший элемент
[В этом случае мы выскочим из стека, когда встретим следующий меньший элемент, в остальном все будет аналогично следующему большему элементу]
2. Предыдущий больший элемент
[В этом случае мы собираемся пройтись по массиву в обратном порядке и вытолкнуть из стека, когда встретим следующий больший элемент]
3. Предыдущий меньший элемент
[Здесь мы собираемся пройтись по массиву в обратном порядке и вытолкнуть из стека, когда встретим следующий меньший элемент]
Ссылки:
1. Монотонный стек от Ян Чжоу
2. Монотонный стек (Leetcode Next больше / меньше )
3. Java Solution с использованием монотонного стека
4. Java-решение без использования стека
To connect or collaborate ping me: LinkedIn Twitter GitHub
