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

Question

究竟什么是单​​调堆栈？（例如，它与单调队列有何不同？）

例如，考虑以下整数数组：[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值。这实际上是否正确实现了单调堆栈？

标签： python-3.xalgorithmdata-structuresstack

Answer 1

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

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

1. 是单调递减的
2. 尊重输入的 FIFO 排序
3. 包括最后堆叠的项目（即它可以清除大于它的项目）。

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