python-3.x - 单调堆栈和队列。定义和例子

Question

什么是单调堆栈？ (例如，它与单调队列有什么不同？)

例如。考虑以下整数数组:[0, 2, 1, 3, 4] .如果我从左到右处理这个数组，将它插入到一个单调递减的堆栈中，我应该在堆栈中看到什么，为什么？

Here是 Python 中单调递减堆栈的一个示例，显然用于解决 the odd-even jump problem 的许多解决方案中。 :

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值(value)。这实际上是否正确实现了单调堆栈？

Answer 1

在您的示例中 result是 不是 单调堆栈。我认为您感到困惑，因为问题解决方案的描述暗示使用“单调堆栈”和函数名称 make可能会给您的印象是它正在构建它。但事实并非如此。

A 单调递减堆栈 是一个堆栈，当弹出其元素时将产生一个序列:

是 单调递减

尊重输入的 FIFO 顺序

包括堆叠的最后一个项目(即它可以清除大于它的项目)。

在这种情况下，函数 make使用单调堆栈的构造(变量 stack )来识别数组 A 中每个(索引)值的“下一个更大的索引”(存储在 result 中)。这是因为构建单调堆栈的过程碰巧识别输入的“下一个更大的索引”，因为您在堆叠新项目时清除不应包含在输出中的项目(根据上述属性)。