单调堆栈和队列。定义和例子

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

Answer 1

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

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

1. 是单调递减的
2. 遵守输入的 LIFO（后进先出）顺序
3. 包括最后堆叠的项目（即它可以清除大于它的项目）。

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