单调的堆栈和队列.定义和例子 [英] Monotonic stacks and queues. Definition and examples

问题描述

究竟什么是单​​调堆栈?(例如，它与单调队列有何不同?)

What exactly is a monotonic stack? (and e.g. how is it different from a monotonic queue?)

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

E.g. consider the following array of integers: [0, 2, 1, 3, 4]. If I process this array left to right inserting it into a monotonically decreasing stack, what am I supposed to see in the stack, and why?

这里Python 中单调递减堆栈的示例，显然用于解决 奇偶跳转的许多解决方案问题:

Here's an example for a monotonically decreasing stack in Python that apparently is used in many solutions that solve 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 值.这实际上是否正确实现了单调堆栈?

If I run it on the following input A = [0, 2, 1, 3, 4] I get [2, 3, 3, 4, None]. I find it odd because it includes two 3's, and a None value. Is this actually correctly implementing a monotonic stack?

推荐答案

在您的示例中，result 不是 单调堆栈.我认为您感到困惑是因为问题解决方案的 description 暗示使用单调堆栈"，而函数名称 make 可能会给您的印象是它正在建造它.但事实并非如此.

In your example result is not a monotonic stack. I think you got confused because the description of the solution to the problem alludes to the use of a "monotonic stack", and the function name make may give you the impression that it's building it. But that's not the case.

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

A monotonic decreasing stack is a stack that will produce, when popping its elements a sequence that:

1. 单调递减
2. 尊重输入的 FIFO 顺序
3. 包括最后堆叠的项目(即它可以清除大于它的项目).

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

In this case, the function make uses the construction of a monotonic stack (the variable stack) to identify the "next greater index" (stored in result) for each (index) value in the array A. This is because the process of building the monotonic stack happens to identify the "next greater index" of the input as you are purging items that should not be included in the output (as per the properties above) as you stack new items.

这篇关于单调的堆栈和队列.定义和例子的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！