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

> Discover practical applications of a monotonic stack. Learn how it solves nearest greater element problems and trapping rain water in O(N) time. Optimize your algorithms today.

- Repository: [lucifer/leetcode](https://github.com/azl397985856/leetcode)
- Tags: deep-dive
- Published: 2026-03-06

---

**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`](https://github.com/azl397985856/leetcode/blob/main/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`](https://github.com/azl397985856/leetcode/blob/main/problems/739.daily-temperatures.md) and [`problems/901.stock-price-span.md`](https://github.com/azl397985856/leetcode/blob/main/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`](https://github.com/azl397985856/leetcode/blob/main/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`](https://github.com/azl397985856/leetcode/blob/main/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`](https://github.com/azl397985856/leetcode/blob/main/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`](https://github.com/azl397985856/leetcode/blob/main/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`](https://github.com/azl397985856/leetcode/blob/main/thinkings/monotone-stack.md). Here are the canonical implementations:

**Python template for Next Greater Element:**

```python
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:**

```javascript
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.