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

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

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

Here http://www.leetcode-solution.com/2019/06/01/1017-odd-even-jump.html这是 Python 中单调递减堆栈的一个示例，显然它被用在许多解决方案中奇偶跳问题 https://leetcode.com/problems/odd-even-jump/:

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] I get [2, 3, 3, 4, None]。我觉得很奇怪，因为它包含两个 3，和一个None价值。这实际上正确地实现了单调堆栈吗？

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

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

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

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