My Wiki

Monotonic Stack

●STABLE

3 min read

A Monotonic Stack is a stack where elements are always sorted (either in increasing or decreasing) inside a stack.

The Rule: Before pushing a new element X, you pop all elements from the stack that violate the order you want.

Use Case: “Next Greater Element”

Imagine an array: [2, 1, 5, 6, 2, 3] → For every number, find the next number to the right that is bigger.

Manual Walkthrough (Monotonic Decreasing Stack logic): We want to keep smaller elements in the stack, waiting for a big number to come pop them.

  1. Stack: []. Value 2. Push 2. (Stack: [2])
  2. Stack: [2]. Value 1. Is 1 > 2? No. Push 1. (Stack: [2, 1]) → Notice it’s decreasing.
  3. Stack: [2, 1]. Value 5.
    • Is 5 > 1? YES. 1’s next greater element is 5. Pop 1.
    • Is 5 > 2? YES. 2’s next greater element is 5. Pop 2.
    • Push 5. (Stack: [5])
  4. Stack: [5]. Value 6.
    • Is 6 > 5? YES. 5’s next greater is 6. Pop 5.
    • Push 6. (Stack: [6])

See the pattern? The stack stores elements that haven’t found their greater neighbor yet.

def next_greater_element(nums: list[int]) -> list[int]:
    n = len(nums)
    # 1. Pre-fill result with -1
    result = [-1] * n 
    # 2. Stack stores INDICES, not values
    stack = [] 
 
    for current_index in range(n):
        current_val = nums[current_index]
        
        # While stack is not empty AND the current value is bigger 
        # than the value associated with the index on top of the stack
        while stack and nums[stack[-1]] < current_val:
            index_to_update = stack.pop()
            result[index_to_update] = current_val
            
        stack.append(current_index)
        
    return result
pub fn next_greater_element(nums: Vec<i32>) -> Vec<i32> {
    let n = nums.len();
    let mut stack: Vec<usize> = Vec::new();
    let mut result = vec![-1; n];
 
    for current_index in 0..n {
        let current_val = nums[current_index];
 
        while !stack.is_empty() && nums[*stack.last().unwrap()] < current_val {
            let index_to_update = stack.pop().unwrap();
            result[index_to_update] = current_val;
        }
 
        stack.push(current_index);
    }
 
    result
}
 
fn main() {}

Monotonic Stack Patterns

The Core Rule

Use this data structure when you need to find the nearest element (to the left or right) that breaks a trend (is smaller or larger) for every element in the dataset.

Which Stack to Use?

1. Monotonic Decreasing Stack

Keeps elements in decreasing order: [10, 8, 5, 3]

  • Trigger: You are looking for the Next Greater Element.
  • Logic: Smaller elements wait in the stack. When a Big number comes, it pops the small ones. The Big number is the “Next Greater” for everyone it popped.
  • Use Case: Daily Temperatures, Next Greater Element I/II.

2. Monotonic Increasing Stack

Keeps elements in increasing order: [1, 4, 7, 10]

  • Trigger: You are looking for the Next Smaller Element.
  • Logic: Bigger elements wait in the stack. When a Small number comes, it pops the big ones. The Small number is the “Next Smaller” for everyone it popped.
  • Use Case: Largest Rectangle in Histogram, Final Prices with Discount.

Complexity

  • Naive Solution: Double Loop
  • Monotonic Stack: Linear Scan
    • Why? Each element is pushed once and popped once.
← Stacks
Min Stack →