什么是单调堆栈? (例如,它与单调队列有什么不同?)
例如。考虑以下整数数组:[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)。这实际上是否正确实现了单调堆栈?
最佳答案
在您的示例中 result
是 不是 单调堆栈。我认为您感到困惑,因为问题解决方案的描述暗示使用“单调堆栈”和函数名称 make
可能会给您的印象是它正在构建它。但事实并非如此。
A 单调递减堆栈 是一个堆栈,当弹出其元素时将产生一个序列:
在这种情况下,函数
make
使用单调堆栈的构造(变量 stack
)来识别数组 A 中每个(索引)值的“下一个更大的索引”(存储在 result
中)。这是因为构建单调堆栈的过程碰巧识别输入的“下一个更大的索引”,因为您在堆叠新项目时清除不应包含在输出中的项目(根据上述属性)。
关于python-3.x - 单调堆栈和队列。定义和例子,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/61199170/