Monotonic Stack

A stack is a linear data structure and allows LIFO (Last-In-First-Out) operations. Monotonic stacks are stacks where elements are monotonically increasing/decreasing from the bottom to the top.

Monotonic stack is a prevalent algorithm to deal with arrays when we want to find:

• The previous smaller element (PSE) — monotonic increasing stack
• The previous greater element (PGE) — monotonic decreasing stack
• The next smaller element (NSE) — monotonic increasing stack
• The next greater element (NGE) — monotonic decreasing stack

Next greater element — NGE

def nextGreaterElement(arr):
    nge = [-1] * len(arr)
    mono = []
    for i, val in enumerate(arr):
        while mono and val > arr[mono[-1]]:
            nge[mono.pop()] = i # Store the index of the next greater element
        mono.append(i)
    return nge

# nextGreaterElement([2,3,6,1,7,5]) => [1, 2, 4, 4, -1, -1]

Next smaller element — NSE

def nextSmallerElement(arr):
    nse = [-1] * len(arr)
    mono = []
    for i, val in enumerate(arr):
        while mono and val < arr[mono[-1]]:
            nse[mono.pop()] = i # Store the index of the next smaller element
        mono.append(i)
    return nse

# nextSmallerElement([2,3,6,1,7,5]) => [3, 3, 3, -1, 5, -1]

Previous greater element — PGE

def previousGreaterElement(arr):
    pge = [-1] * len(arr)
    mono = []
    for i, val in enumerate(arr):
        while mono and val >= arr[mono[-1]]:
            mono.pop()
        if mono:
            pge[i] = mono[-1]
        mono.append(i)
    return pge

# previousGreaterElement([2,3,6,4,5,4]) => [-1, -1, -1, 2, 2, 4]

Previous smaller element — PSE

def previousSmallerElement(arr):
    pse = [-1] * len(arr)
    mono = []
    for i, val in enumerate(arr):
        while mono and val <= arr[mono[-1]]:
            mono.pop()
        if mono:
            pse[i] = mono[-1]
        mono.append(i)
    return pse

# previousSmallerElement([2,3,6,4,5,4]) => [-1, 0, 1, 1, 3, 1]

Note

1. The general rule is to iterate through the input array from left to right. For each arr[i], compare it with the top of the monotonic stack mono
2. Both NGE and PGE use monotonic decreasing stack.

NGE treats arr[i] as the next greater element for the top of the mono stack nge[mono.pop()]=i, and keep popping values out until arr[i] is smaller, therefore it pop() and records at the same time; PGE finds the previous greater element for arr[i] by popping all values in the stack that is smaller, until find the top element to be greater than arr[i], therefore it pops() first and then records pge[i]=mono[-1].

3. Both NSE and PSE use monotonic increasing stack.