Monotonic Stack / Queue Pattern

Monotonic Stack / Queue

Problem Scenario / Typical Use Case

Imagine you are analyzing daily stock prices and want to determine, for each day, the next day when the stock price will be higher.

A naive approach would check all following days for each price, leading to (O(n^2)) complexity. The Monotonic Stack / Queue pattern provides an efficient way to maintain candidates in a sorted order, allowing you to answer these “next greater” or “next smaller” queries in linear time.

Basic Idea

A monotonic stack or queue is a data structure that maintains elements in a strictly increasing or decreasing order:

• Monotonic Stack: Last-in-first-out (LIFO) structure where elements are pushed and popped to maintain order.
• Monotonic Queue: First-in-first-out (FIFO) structure with similar monotonic properties.

Typical operations include:

• Finding the next or previous greater/smaller element.
• Sliding window maximum/minimum problems.
• Histogram area calculations or pattern detection in sequences.

The core idea is efficiently keeping track of potential candidates while iterating once over the sequence.

Advantages

• Linear Time Complexity: Reduces naive (O(n^2)) approaches to (O(n)).
• Space Efficient: Only keeps necessary candidates in the stack/queue.
• Versatility: Applicable to arrays, linked lists, and sliding windows problems.

Limitations / Considerations

• Requires careful push/pop logic to maintain the monotonic property.
• Mostly effective for problems asking for “next/previous” relations or maximum/minimums.
• Understanding stack/queue behavior is crucial—mismanagement can lead to incorrect results.

Practical Examples / Thought Triggers

1. Next Greater Element in Stock Prices: Monotonic stack allows determining the next day with a higher price in (O(n)).
2. Sliding Window Maximum: Combine monotonic queue with window boundaries to find max efficiently.
3. Largest Rectangle in Histogram: Use a monotonic stack to track bars and calculate areas incrementally.

Thought Triggers:

• Should I use a stack (LIFO) or queue (FIFO)? Depends on whether the problem is positional or range-based.
• Can this combine with Sliding Window for fixed-size intervals?
• How do I handle duplicates or equal elements while maintaining monotonicity?

Implementation Example

Here’s a Python example for next greater element using a monotonic stack:

def next_greater_elements(prices):
    result = [-1] * len(prices)
    stack = []  # stores indices

    for i, price in enumerate(prices):
        while stack and prices[stack[-1]] < price:
            index = stack.pop()
            result[index] = price
        stack.append(i)

    return result

# Example usage
stock_prices = [100, 80, 120, 90, 130]
print(next_greater_elements(stock_prices))
# Output: [120, 120, 130, 130, -1]

This demonstrates the monotonic stack principle: only keeping candidates that could potentially satisfy the “next greater” condition.

Related Articles

• Sliding Window: Monotonic queue is often combined with sliding windows for maximum/minimum range queries.
• Two Pointers: Can sometimes define the window boundaries for monotonic structures.
• Stack / Queue Fundamentals: Understanding standard stack/queue operations is essential before implementing monotonic variations.