单调堆栈和队列。定义和例子 [英] 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，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，1，3，4] I得到 [2、3、3、4，无] 。我觉得这很奇怪，因为它包含两个3和一个无值。这实际上正确实现了单调堆栈吗？

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?

推荐答案

在您的示例中，结果 不是单调堆栈。我认为您很困惑，因为对该问题的解决方案的说明暗示了使用单调堆栈和函数名称 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屋！