# What Makes the Monotonic Stack Technique Effective: Insights from the leetcode-master Repository

> Unlock O(n) time complexity with the monotonic stack technique. Efficiently solve next greater/smaller element problems by pushing and popping each element once, avoiding O(n²) nested loops.

- Repository: [程序员Carl/leetcode-master](https://github.com/youngyangyang04/leetcode-master)
- Tags: deep-dive
- Published: 2026-03-05

---

**The monotonic stack technique achieves O(n) time complexity by ensuring each element is pushed once and popped at most once, immediately resolving "next greater" or "next smaller" queries that would otherwise require O(n²) nested loops.**

The **monotonic stack** is a specialized data structure pattern that preserves either strictly increasing or strictly decreasing values while scanning a one-dimensional array. In the `youngyangyang04/leetcode-master` repository, this technique powers optimized solutions for classic problems ranging from daily temperature forecasts to histogram area calculations. Understanding what makes the monotonic stack technique effective reveals how it eliminates nested loops and replaces them with elegant single-pass algorithms.

## Core Mechanism: Ordered Traversal in Linear Time

A monotonic stack operates on a simple invariant: elements remain sorted in a specific direction (increasing or decreasing) from bottom to top. This ordering enables **immediate resolution** of pending queries when a "breaking" element arrives.

According to the implementation in `problems/0739.每日温度.md`, the algorithm maintains indices of temperatures in a **decreasing stack** (values descend from bottom to top). When encountering a warmer temperature, the stack pops all indices with colder values, calculating the distance between the current day and the popped day.

```cpp
vector<int> result(T.size(), 0);
stack<int> st; // indices of decreasing temperatures
for (int i = 0; i < T.size(); ++i) {
    while (!st.empty() && T[i] > T[st.top()]) {
        result[st.top()] = i - st.top();
        st.pop();
    }
    st.push(i);
}

```

Each index enters and exits the stack exactly once, yielding **O(n)** time complexity regardless of input size.

## Problem Categories Solved by Monotonic Stacks

The repository categorizes monotonic stack applications into distinct families based on the relationship being queried.

### Next Greater Element to the Right

Problems **739 (Daily Temperatures)** and **496 (Next Greater Element I)** seek the first larger element appearing after the current index. An **increasing stack** (storing indices of decreasing values) defers resolution until a larger value triggers the pop operation.

As implemented in `problems/0496.下一个更大元素I.md`, the pattern resolves answers in reverse order of occurrence while maintaining chronological integrity.

### Circular Array Extensions

Problem **503 (Next Greater Element II)** extends the pattern to circular arrays by simulating two passes through the data. The implementation in `problems/0503.下一个更大元素II.md` iterates `2 × n` times while using modulo arithmetic to access indices, allowing the monotonic stack to find "next greater" elements that wrap around the array boundary without additional data structures.

```cpp
int n = nums.size();
vector<int> ans(n, -1);
stack<int> st;
for (int i = 0; i < 2 * n; ++i) {
    int idx = i % n;
    while (!st.empty() && nums[idx] > nums[st.top()]) {
        ans[st.top()] = nums[idx];
        st.pop();
    }
    if (i < n) st.push(idx);
}

```

This technique restricts pushes to the first pass (`i < n`) while allowing resolutions across the virtual circular boundary.

### Nearest Smaller Elements for Area Calculations

Problem **84 (Largest Rectangle in Histogram)** requires finding the nearest smaller bar on both sides to determine the maximum width where each bar acts as the limiting height. The solution in `problems/0084.柱状图中最大的矩形.md` utilizes a **decreasing stack** that pops when encountering a shorter bar, calculating the area with the popped height as the minimum.

```cpp
int maxArea = 0;
stack<int> st;
for (int i = 0; i <= h.size(); ++i) {
    int cur = (i == h.size() ? 0 : h[i]);
    while (!st.empty() && cur < h[st.top()]) {
        int height = h[st.top()]; st.pop();
        int left = st.empty() ? -1 : st.top();
        int width = i - left - 1;
        maxArea = max(maxArea, height * width);
    }
    st.push(i);
}

```

The sentinel value `0` at position `h.size()` ensures all remaining bars are processed, guaranteeing every potential rectangle is evaluated.

### Dual-Side Boundary Detection

Problem **42 (Trapping Rain Water)** uses the monotonic stack to identify the nearest higher bar on both sides. The implementation in `problems/0042.接雨水.md` maintains a decreasing stack of indices; when a taller bar arrives, it calculates trapped water between the current bar and the previous higher boundary revealed by the stack.

```cpp
int total = 0;
stack<int> st;
for (int i = 0; i < h.size(); ++i) {
    while (!st.empty() && h[i] > h[st.top()]) {
        int bottom = st.top(); st.pop();
        if (st.empty()) break;
        int left = st.top();
        int width = i - left - 1;
        int bounded = min(h[i], h[left]) - h[bottom];
        total += width * bounded;
    }
    st.push(i);
}

```

## Architectural Advantages in the Repository

The `leetcode-master` implementations demonstrate four critical efficiency principles:

- **Single-pass resolution**: Each element enters the stack once and exits once, eliminating the O(n²) nested loop requirement for "nearest greater/smaller" queries.
- **Space-for-time trade-off**: The O(n) auxiliary space stores at most n indices, a negligible cost compared to the quadratic time saved.
- **Localized computation**: Answers are computed at the exact moment the boundary condition is met, ensuring no redundant comparisons.
- **Minimal state maintenance**: Unlike dynamic programming approaches requiring full auxiliary arrays, the stack only stores unresolved indices, reducing memory footprint.

## Summary

- **Monotonic stacks** maintain strictly increasing or decreasing order to defer resolution until a boundary element is found.
- The technique guarantees **O(n) time complexity** because each index is pushed and popped at most once.
- **Next greater element** problems use increasing stacks to find the first larger value to the right.
- **Circular arrays** are handled by iterating `2 × n` with modulo indexing, as shown in `problems/0503.下一个更大元素II.md`.
- **Histogram and trapping water** problems utilize decreasing stacks to find nearest smaller or larger boundaries on both sides.
- All implementations reside in the repository's dedicated **"单调栈"** section of [`README.md`](https://github.com/youngyangyang04/leetcode-master/blob/main/README.md), providing consistent C++ and Python examples.

## Frequently Asked Questions

### What is the difference between an increasing and decreasing monotonic stack?

An **increasing stack** stores indices where values rise from bottom to top (used for finding next smaller elements), while a **decreasing stack** stores indices where values fall from bottom to top (used for finding next greater elements). In `problems/0084.柱状图中最大的矩形.md`, a decreasing stack identifies the nearest smaller bar to the left, whereas `problems/0739.每日温度.md` uses a decreasing stack (of temperatures) to find the next warmer day, which effectively tracks increasing temperature values.

### When should I use a monotonic stack instead of brute force?

Use a monotonic stack when the problem requires finding the **first element greater or smaller than the current element** in a specific direction (left or right). Brute force approaches require O(n²) time because they compare each element with all subsequent elements. The monotonic stack technique reduces this to O(n) by maintaining candidates in sorted order and resolving queries immediately when boundary conditions are met.

### How do monotonic stacks handle circular arrays?

Circular arrays are processed by simulating two concatenated passes through the data. As implemented in `problems/0503.下一个更大元素II.md`, iterate from `0` to `2 × n - 1` and use modulo arithmetic (`i % n`) to access array indices. Push indices only during the first pass (`i < n`), but allow resolutions during both passes. This technique finds "next greater" elements that appear after the array wraps around without modifying the input or using extra data structures.

### Can one monotonic stack pass find both left and right boundaries?

A single monotonic stack pass finds boundaries in **one direction only** (typically to the right or left). Problems requiring boundaries on both sides, such as **Largest Rectangle in Histogram**, either use two separate passes (left-to-right and right-to-left) or calculate one boundary implicitly through stack manipulation. In `problems/0084.柱状图中最大的矩形.md`, the single pass computes the right boundary when popping, while the remaining stack contents after the sentinel provide the left boundary information.