Practical Applications of a Monotonic Stack: From Next Greater Element to Trapping Rain Water

A monotonic stack maintains elements in strictly increasing or strictly decreasing order to solve "nearest greater/smaller element" problems in O(N) time by resolving answers immediately when the monotonic invariant is violated.

The monotonic stack is a fundamental algorithmic pattern found throughout the azl397985856/leetcode repository. By enforcing a strict ordering of elements, this specialized stack structure transforms otherwise quadratic scanning algorithms into optimal linear passes, making it essential for solving classic interview problems efficiently.

What Is a Monotonic Stack?

A monotonic stack is a stack data structure that maintains its elements in either monotonically increasing or monotonically decreasing order. Unlike a standard stack that accepts any push order, a monotonic stack actively manages its contents to preserve this invariant.

When processing an array, the algorithm typically iterates left-to-right while maintaining a decreasing stack (for finding next greater elements) or an increasing stack (for finding next smaller elements). When the current element violates the monotonic property—meaning it is larger than the top of a decreasing stack or smaller than the top of an increasing stack—the algorithm repeatedly pops elements until order can be restored.

Core Algorithmic Pattern

The power of the monotonic stack lies in its on-the-fly resolution of answers. When an element is popped from the stack, the current iterating index represents the first position to the right that is greater (or smaller) than the popped value. This allows the algorithm to assign answers immediately rather than performing nested loops.

This pattern guarantees O(N) time complexity because each element is pushed onto the stack exactly once and popped at most once. The auxiliary space is O(N) in the worst case, occurring when the input array is already sorted in the order that prevents any pops until the end of the iteration.

Practical Applications and LeetCode Examples

The azl397985856/leetcode repository demonstrates monotonic stack applications across numerous problem files. Here are the primary practical use cases:

Next Greater Element (LeetCode 496)

In problems/496.next-greater-element-i.md, the monotonic stack solves the classic problem of finding the first element to the right that is greater than the current value. A decreasing stack stores indices of elements waiting for their next greater neighbor. When a larger value appears, it resolves all pending indices by popping them from the stack.

Daily Temperatures (LeetCode 739) and Stock Price Span (LeetCode 901)

Both problems/739.daily-temperatures.md and problems/901.stock-price-span.md utilize the same decreasing stack pattern. For daily temperatures, the stack stores indices of days waiting for a warmer future day. For the stock span problem, the stack tracks days with decreasing prices; popping elements calculates the span of consecutive days with lower or equal prices.

Trapping Rain Water (LeetCode 42)

The solution in problems/42.trapping-rain-water.md uses a monotonic stack to track left boundaries of potential water traps. As the algorithm iterates through bar heights, a decreasing stack stores indices of bars that could form the left wall of a container. When a taller bar appears, it closes containers with all shorter bars in the stack, calculating trapped water volume for each valley.

Largest Rectangle in Histogram (LeetCode 84)

In problems/84.largest-rectangle-in-histogram.md, an increasing stack finds the largest rectangular area under a histogram. The stack maintains bar heights in ascending order. When a shorter bar appears, it triggers pops that determine the right boundary for the popped bars, while the new top of the stack provides the left boundary. This yields the width for calculating the maximum area in linear time.

Remove K Digits (LeetCode 402)

The greedy solution in problems/402.remove-k-digits.md uses an increasing monotonic stack to build the smallest possible number. By removing digits that are larger than their right neighbors (maintained via stack pops), the algorithm ensures the most significant digits are as small as possible while respecting the constraint of removing exactly k digits.

Shortest Unsorted Subarray (LeetCode 581)

In problems/581.shortest-unsorted-subarray.md, monotonic stacks determine the boundaries of the minimal window that needs sorting. One pass with an increasing stack finds the left boundary where order breaks, and a decreasing stack pass (or reverse iteration) finds the right boundary.

Implementation Templates

The repository provides reusable templates in thinkings/monotone-stack.md. Here are the canonical implementations:

Python template for Next Greater Element:

def next_greater(arr):
    stack = []
    ans = [-1] * len(arr)                     # default: no greater element

    for i, val in enumerate(arr):
        while stack and val > arr[stack[-1]]:
            idx = stack.pop()
            ans[idx] = i                       # current i is the next greater

        stack.append(i)
    return ans

JavaScript template for Stock Span / Daily Temperatures:

function monotonicStack(nums) {
  const stack = [];
  const result = new Array(nums.length).fill(0);
  for (let i = 0; i < nums.length; i++) {
    while (stack.length && nums[stack[stack.length - 1]] <= nums[i]) {
      const idx = stack.pop();
      result[i] += i - idx;                  // span contributed by popped index
    }
    stack.push(i);
    result[i] += 1;                         // include the current day itself
  }
  return result;
}

Both implementations follow the push-while-maintaining-monotonicity pattern, ensuring linear time complexity.

Summary

• A monotonic stack maintains strictly increasing or decreasing order to enable O(N) solutions for nearest-element queries.
• The core pattern involves popping elements when the current value violates the monotonic invariant, which immediately resolves the answer for popped indices.
• Key applications include Next Greater Element, Daily Temperatures, Trapping Rain Water, Largest Rectangle in Histogram, and Remove K Digits, with implementations found in the azl397985856/leetcode repository.
• The algorithm guarantees O(N) time and O(N) space, with each element pushed and popped at most once.

Frequently Asked Questions

What is the time complexity of monotonic stack algorithms?

Monotonic stack algorithms operate in O(N) time where N is the number of elements in the input array. Each index is pushed onto the stack exactly once and popped at most once, resulting in a linear total operation count despite the nested appearance of the while-loop.

When should I use a monotonic stack instead of a regular stack?

Use a monotonic stack when the problem requires finding the nearest greater or smaller element to the left or right of each array position, or when calculating spans, areas, or volumes that depend on boundaries defined by increasing or decreasing values. Regular stacks suffice for simple LIFO operations without ordering constraints.

Can monotonic stacks be used for 2D problems?

Yes, monotonic stacks extend to 2D problems such as maximal rectangle in a binary matrix (LeetCode 85), where the algorithm first computes histogram heights for each row and then applies the monotonic stack solution for Largest Rectangle in Histogram to each row. This maintains the O(N) time complexity per row.

How do I choose between increasing and decreasing monotonic stacks?

Choose a decreasing stack (maintaining elements from large to small) when searching for the next greater element to the right, as this allows larger incoming values to trigger pops and resolve pending indices. Choose an increasing stack (small to large) when searching for the next smaller element, or when calculating areas in histograms where shorter bars trigger resolution of wider rectangles.

{
  "mcpServers": {
    "instagit": {
      "command": "npx",
      "args": ["-y", "instagit@latest"]
    }
  }
}