单调栈和队列。定义和示例

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

- Josh

---

单调栈是一个按照递增或递减顺序排列的栈。假设栈是按照递减顺序排列的，那么栈中的元素应该是按照递减顺序排列的。因此，当您想要推入一个元素时，如果它大于栈顶元素，则无法将其推入栈中，因此您需要从栈中弹出元素，直到达到一个小于要推入的元素的值为止。 - Wasim Ahmad

结果数组基本上是告诉索引为i的元素下一个更大的元素是什么。顺便说一句，没有单调栈的实现或其他什么，如果你想按递增或递减顺序插入，你需要弹出以使栈始终保持有序。 - Wasim Ahmad

感谢@WasimAhmad - 当您说：“结果数组基本上是告诉索引为i的元素的下一个更大元素。”这很有帮助。可以这么说，这个结果数组不是单调栈本身（它只是提供了一种按单调方式遍历原始数组的方法）吗？另外，当您说：“没有实现单调栈”时，您确切地是指什么？您是否在说，像这种情况一样，实现只是一种使用类似堆栈的接口单调读取数据的“方法”？只想确保我正确理解了您的观点。 - Josh

结果不是一个栈。实现指的是你不需要做任何特殊的事情来实现单调栈。你只需要插入单调数据，例如1 2 3 6 10 11。 - Wasim Ahmad

Answer 1

在你的例子中，result 不是单调栈。我认为你可能会因为解决问题的描述涉及使用 "单调栈"，以及函数名 make 可能会让你觉得它正在构建一个单调栈而感到困惑。但事实并非如此。

一个单调递减栈是这样一种堆栈：当弹出其元素时，它会产生一个满足以下条件的序列：

1. 单调递减 2. 遵守输入的 LIFO（后进先出）顺序 3. 包括最后一个入栈的项（即它可以清除比它大的项）。

在本例中，函数 make 使用单调栈的构造（变量 stack）来为数组 A 中的每个 (index) 值识别 "下一个更大的索引"（存储在 result 中）。这是因为构建单调栈的过程恰好可以识别输入的 "下一个更大的索引"，当您堆叠新项并清除不应包括在输出中的项（根据上述属性）时。

- Josh

---

你的一个问题是，“它与单调队列有什么不同？” 你能否进一步阐述一下（我目前在答案中没有看到）？ - abhishek_naik

单调队列概念的良好写作：链接 - Md.Habibur Rahman