Monotoni c стеки и очереди. Определение и примеры

Question

Что такое монотонный c стек? (и, например, чем она отличается от монотонной c очереди?)

Например, рассмотрим следующий массив целых чисел: [0, 2, 1, 3, 4]. Если я обработаю этот массив слева направо, вставив его в монотонно уменьшающийся стек, что я должен видеть в стеке и почему?

---

Здесь - это пример для монотонно убывающий стек в Python, который, очевидно, используется во многих решениях, которые решают проблему нечетно-четного скачка :

def make(A):
    result = [None] * N
    stack = []  # invariant: stack is decreasing
    for i in A:
        while stack and i > stack[-1]:
            result[stack.pop()] = i
        stack.append(i)
    return result

Если я запускаю его на следующем входе A = [0, 2, 1, 3, 4] Я получаю [2, 3, 3, 4, None]. Я нахожу это странным, потому что он включает в себя два 3 и значение None. Действительно ли это правильно реализует монотонный c стек?

Answer 1

В вашем примере result - это , а не монотонный c стек. Я думаю, вы запутались, потому что описание решения проблемы намекает на использование «монотонного c стека», а имя функции make может создать у вас впечатление, что она его строит , Но это не так.

A monotoni c убывающий стек - это стек, который при выталкивании его элементов создаст последовательность, которая:

1. * монотонно убывающая
2. соблюдает порядок ввода FIFO
3. включает в себя последний сложенный элемент (т. Е. Он может очищать элементы больше его).

В этом случае функция make использует конструкцию монотонного стека c (переменная stack) для определения «следующего большего индекса» (хранится в result) для каждого значения (индекса) в массив A. Это связано с тем, что процесс построения монотонного стека c идентифицирует «следующий больший индекс» входных данных при очистке элементов, которые не должны быть включены в выходные данные (согласно свойствам выше), как Вы складываете новые предметы.