Monotonic Stack

A stack whose contents are kept sorted. Answers “next greater / previous smaller” style questions for the whole array in $O (n)$ total.

Previous smaller element

vector<int> prevSmaller(vector<int>& a) {
    int n = a.size();
    vector<int> res(n, -1);
    stack<int> st;                                   // indices, values increasing
    for (int i = 0; i < n; i++) {
        while (!st.empty() && a[st.top()] >= a[i]) st.pop();
        res[i] = st.empty() ? -1 : st.top();
        st.push(i);
    }
    return res;
}

Each index is pushed once and popped at most once → $O (n)$ .

The four variants

Want	Direction	Pop while
Previous smaller	left to right	`a[st.top()] >= a[i]`
Previous greater	left to right	`a[st.top()] <= a[i]`
Next smaller	right to left	`a[st.top()] >= a[i]`
Next greater	right to left	`a[st.top()] <= a[i]`

Use >= vs > deliberately: strict comparison keeps equal elements, which matters when the problem must not double-count identical values (as in the histogram problem below).

The canonical applications

Largest rectangle in a histogram

For each bar, the widest rectangle with that bar as the minimum spans from the previous smaller to the next smaller element:

long long largestRectangle(vector<int>& h) {
    int n = h.size();
    stack<int> st;
    long long best = 0;
    for (int i = 0; i <= n; i++) {
        int cur = (i == n) ? -1 : h[i];              // sentinel flushes the stack
        while (!st.empty() && h[st.top()] >= cur) {
            int height = h[st.top()]; st.pop();
            int left = st.empty() ? -1 : st.top();
            best = max(best, (long long)height * (i - left - 1));
        }
        st.push(i);
    }
    return best;
}

The sentinel at $i = n$ avoids a separate flush loop.

Trapping rain water

Pop while the current bar is taller; each pop bounds a trapped basin.

Maximal rectangle in a binary matrix

Build a histogram of consecutive 1s per row and run the histogram algorithm on each row. $O (nm)$ .

Sum over all subarrays of the minimum

For each element, count the subarrays in which it is the minimum: $(i - prevSmaller) \times (nextSmaller - i)$ . Use strict on one side and non-strict on the other so ties are counted exactly once.

long long total = 0;
for (int i = 0; i < n; i++)
    total += (long long)a[i] * (i - left[i]) * (right[i] - i);

This “count the subarrays each element dominates” pattern generalises to sums of maxima, of ranges, and of gcds.

Other uses

Stock span / daily temperatures
Remove $k$ digits to make the smallest number
Building a Cartesian tree in $O (n)$ — the stack construction directly yields the tree, which is the basis of the RMQ-to-LCA reduction
Validating and matching brackets (the degenerate case)
Convex hull trick — the hull maintenance is a monotonic stack on slopes
Andrew’s monotone chain — the same stack discipline on cross products

The debugging rule

Draw the array, mark for each index what its answer should be, then check that the stack contains exactly the “still unresolved” indices at each step. Almost every bug is a < that should be <=, or popping after reading instead of before.

See also: Monotonic Queue · Largest Rectangle · Minimum Stack

whoashish's cp notes

Directory