Introduction to Monotonic Structures

A monotonic stack or deque maintains elements in strictly increasing or decreasing order. They're perfect for "next greater/smaller element" problems.

Monotonic Increasing Stack

Elements increase from bottom to top.

def monotonic_increasing_stack(nums):
    stack = []

    for num in nums:
        # Pop elements that violate increasing order
        while stack and stack[-1] >= num:
            stack.pop()
        stack.append(num)

    return stack

# Example
print(monotonic_increasing_stack([5, 3, 7, 1, 4]))
# [1, 4] - only increasing elements remain

Monotonic Decreasing Stack

Elements decrease from bottom to top.

def monotonic_decreasing_stack(nums):
    stack = []

    for num in nums:
        # Pop elements that violate decreasing order
        while stack and stack[-1] <= num:
            stack.pop()
        stack.append(num)

    return stack

# Example
print(monotonic_decreasing_stack([5, 3, 7, 1, 4]))
# [7, 4] - only decreasing elements remain

Next Greater Element

Find the next greater element for each element in array.

def nextGreaterElements(nums):
    """For each element, find next greater element"""
    result = [-1] * len(nums)
    stack = []  # Store indices

    for i in range(len(nums)):
        # Pop smaller elements and set their result
        while stack and nums[stack[-1]] < nums[i]:
            index = stack.pop()
            result[index] = nums[i]

        stack.append(i)

    return result

# Example
print(nextGreaterElements([2, 1, 2, 4, 3]))
# [4, 2, 4, -1, -1]

Daily Temperatures

Find how many days until a warmer temperature.

def dailyTemperatures(temperatures):
    """Days until warmer temperature"""
    result = [0] * len(temperatures)
    stack = []  # Monotonic decreasing (indices)

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

        stack.append(i)

    return result

print(dailyTemperatures([73, 74, 75, 71, 69, 72, 76, 73]))
# [1, 1, 4, 2, 1, 1, 0, 0]

Monotonic Deque (Sliding Window Maximum)

Use deque for both ends access.

from collections import deque

def maxSlidingWindow(nums, k):
    """Maximum in each sliding window of size k"""
    dq = deque()  # Store indices, decreasing values
    result = []

    for i in range(len(nums)):
        # Remove out of window
        while dq and dq[0] <= i - k:
            dq.popleft()

        # Maintain decreasing order
        while dq and nums[dq[-1]] < nums[i]:
            dq.pop()

        dq.append(i)

        if i >= k - 1:
            result.append(nums[dq[0]])

    return result

print(maxSlidingWindow([1,3,-1,-3,5,3,6,7], 3))
# [3, 3, 5, 5, 6, 7]

When to Use

Use monotonic stacks/deques when you need to:

• Find next/previous greater/smaller element
• Maintain min/max in sliding window
• Track largest rectangle in histogram
• Process elements in specific order

Pattern Recognition:

• "Next greater/smaller"
• "Sliding window maximum/minimum"
• "Largest rectangle"
• "Stock span problem"

Key Takeaway

Monotonic structures help solve problems that require tracking relationships between elements efficiently. The key is maintaining order while processing and popping elements that can't be the answer.