Monotonic stack

A monotonic stack keeps its elements in sorted order—either strictly non-decreasing (often called “increasing”) or strictly non-increasing (“decreasing”) from bottom to top. When a new value would break that rule, you pop from the top until the rule holds again (or the stack empties). That discipline turns many “for every element, find the nearest …” problems into a single O(n) left-to-right scan. The same idea shows up in markets (next higher price, stock span), weather series, compilers, navigation search, and streaming analytics—see §4–§8 below after the C walkthrough.

1) Increasing vs decreasing

This lesson implements next greater element to the right, which uses a strictly decreasing stack of indices (values fall as you go up the stack).

2) Scan rule (next greater to the right)

Walk i = 0 … n−1. The stack stores indices still waiting for their answer. Before pushing i, every index on top whose value is smaller than arr[i] has just found its next greater: it is arr[i].

Snapshot for arr[] = { 4, 5, 2, 25, … } — stack holds values at indices (bottom → top):

3) Example in C

The program fills nge[i] with the next strictly greater value to the right of arr[i], or −1 if none exists. The stack stores indices; compare through arr[stack[top]].

#include <stdio.h>

#define N 8

static int arr[N] = { 4, 5, 2, 25, 7, 2, 13, 12 };
static int nge[N];
static int stack[N];
static int top = -1;

// One left-to-right pass: decreasing stack of indices
static void next_greater_to_the_right(void) {
    int i;

    for (i = 0; i < N; i++)
        nge[i] = -1;

    for (i = 0; i < N; i++) {
        while (top >= 0 && arr[stack[top]] < arr[i]) {
            nge[stack[top]] = arr[i];
            top--;
        }
        stack[++top] = i;
    }
}

int main(void) {
    int i;

    next_greater_to_the_right();
    for (i = 0; i < N; i++)
        printf("%d -> %d\n", arr[i], nge[i]);
    return 0;
}

First lines of output: 4 -> 5, 5 -> 25, 2 -> 25, 25 -> -1, …

Trace (abbreviated)

Stack lists indices (values in parentheses). Pops happen only when the new arr[i] is strictly greater.

4) Stock systems & trading

In trading and risk systems, daily (or intraday) prices form a sequence—exactly the kind of array monotonic stacks handle well. You often need next event or span answers for every day in one pass.

Complexity: A naive approach that re-checks each past day for every i can be O(n²). A monotonic stack visits each index a bounded number of times—typically O(n) time and O(n) stack space for the whole series.

5) Weather forecasting & climate

Meteorological time series behave like stock curves: you ask when the next warmer (or colder) day arrives, or how long a cool spell lasts. The “daily temperatures” pattern is the same algorithmic core as next-greater on dates.

6) Compiler design & expression parsing

Compilers walk structured text and numbers; “what is the nearest dominating operator or boundary?” often reduces to nearest smaller / greater style logic on a stream or tree—monotonic stacks keep candidates in order as the scan advances.

7) Navigation & path optimization

When you sweep a route or a grid by cost or elevation, you often discard options that can never be optimal once a better frontier appears—LIFO with monotonic ordering is the right mental model for “drop dominated states.”

8) Memory optimization & system design

At scale you want ordered views of a sliding stream without sorting the whole window every step. Monotonic stacks (or deques) maintain “only what can still matter” for the next insertions.

9) Trade-offs and practice

• Pros — Linear time with a small stack; same skeleton for temperatures, largest rectangle, and “cart stock” style tasks.
• Cons — You must pick the correct monotonic direction and tie-breaking (< vs <=) for each problem statement.

Related in this track: Stack applications · Postfix evaluation · Brackets validation.