CODEWITHSUNDEEP
python-3.xalgorithmdata-structuresstack
Josh
Josh

Reputation: 12781

Monotonic stacks and queues. Definition and examples

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

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?

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

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?

Upvotes: 13

Views: 4462

Answers (1)

Josh
Josh

Reputation: 12781

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. is monotonically decreasing
  2. respects the LIFO (Last In First Out) ordering of the input
  3. includes the last item stacked (i.e. it can purge items greater than it).

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.

Upvotes: 8

Related Questions