Monotonic Stacks in Python

In this article, we’ll explore monotonic stacks, how they work, and how to implement them in Python.

1. What is a Monotonic Stack?

A Stack is a collection of elements that follow the ‘Last In First Out’ (LIFO) principle. It can be easily implemented either through an array or a linked list.

A Monotonic Stack is a data structure used to store elements in a specific order – either always increasing or always decreasing.

Imagine a stack of blocks where each block is smaller than the one below it. For this type of stack, we use mainly Monotonic Stack!

2. How Does a Monotonic Stack Work?

A Monotonic Stack works by maintaining a stack of elements, where each element is either greater than or less than the previous element.

• When a new element is added to the stack, it is compared to the top element of the stack.
• If the new element is greater than the top element, it is pushed onto the stack.
• If the new element is less than the top element, the top element is popped off the stack.
• The new element is pushed onto the stack.

3. How to Create a Monotonic Stack in Python

Let’s create a simple Monotonic Stack in Python. We’ll make a stack where each number is smaller than the one before it.

stack = []

def push(num):
    while stack and stack[-1] >= num:
        stack.pop()
    stack.append(num)

def pop():
    if stack:
        return stack.pop()
    return None

In this code, push adds a number to the stack, but first, it removes any numbers that are bigger than or equal to the new number. pop just removes the top number from the stack.

3.1 Monotonic Stack Python Examples

Suppose you have a list of numbers, and you want to find the next greater number for each element in the list.

Here’s how you can do it using a monotonic stack: 

def next_greater_elements(nums):
    stack = []
    result = [-1] * len(nums)

    for i in range(len(nums)):
        while stack and nums[stack[-1]] < nums[i]:
            index = stack.pop()
            result[index] = nums[i]
        stack.append(i)

    return result

numbers = [2, 1, 2, 4, 3]
print(next_greater_elements(numbers))


## Output
[4, 2, 4, -1, -1]

A few examples of how to use Monotonic Stacks in Python:

• Implementing a Monotonic Stack
• Finding the Maximum Element
• Finding the Minimum Element

4. Monotonic Stack LeetCode Problems

LeetCode problems that involve Monotonic Stacks:

• Valid Parentheses: Given a string of parentheses, determine if the string is valid.
• Largest Rectangle in Histogram: Given a histogram of rectangles, find the area of the largest rectangle.
• Daily Temperatures: Given a list of daily temperatures, find the number of days until the temperature is higher than the current temperature.

5. Advantages of Monotonic Stacks

• Efficient: Require a single pass through the data to find the maximum or minimum element.
• Simple: Simple to implement and understand.
• Flexible: Solve a wide range of problems, from finding the maximum element in a list to validating parentheses.

6. Common Applications of Monotonic Stacks

• Finding the Maximum or Minimum Element: Used to find the maximum or minimum element in a list of data.
• Validating Input: Used to validate input, such as checking if a string of parentheses is valid.

FAQs