Monotonic Stack: Efficient Algorithm for Finding Next Greater Element

Core Logic and Mathematical Principles

Take solving the "Next Greater Element (NGE)" as an example. Define a sequence $A$ of length $N$. For any position $i$, we need to find the smallest $j$ such that $j > i$ and $A[j] > A[i]$.

As a linear data structure that achieves $O(N)$ scanning by maintaining monotonicity of elements within a stack, the core idea of the monotonic stack lies in leveraging the dual monotonicity of time and magnitude to timely process or eliminate decisions, completely optimizing the total time complexity from the naive brute-force $O(N^2)$ to $O(N)$.

Under this mechanism, each decision element "enters the stack at most once and exits the stack at most once" in its entire lifetime, resulting in an amortized complexity of $O(1)$ for each single operation from a global perspective.

The "Timely Fulfillment" Logic of Left-to-Right Scanning

When traversing the sequence from left to right, the stack stores candidate elements in monotonically decreasing order that have not yet found their next greater element on the right.

• When traversing to $A[i]$, if $A[i] > A[\text{stack top}]$, it means the current element $A[i]$ is exactly the "first greater element on the right" that the stack top element has been seeking.
• At this point, the stack top element is "successfully fulfilled": record the answer and pop it. Continue comparing with the new stack top until the stack is empty or the greater-than condition is no longer satisfied. Finally, push $i$ onto the stack.

State Design and Dual Variants

In informatics competitions, monotonic stacks uniformly store element indices rather than values. This is because indices not only allow retrieving values via $A[idx]$, but also enable direct calculation of interval lengths through index subtraction ($i - j$).

By uniformly adopting a left-to-right scanning direction, all four dual problems can be perfectly solved with only minor adjustments to the pop-triggering conditions and answer settlement timing. This classification abstracts the monotonic stack into two core mechanisms:

Core Algorithm Template

// Core logic: Left-to-right scan, solving for the index of the first strictly greater element on the right for each element
// st[] simulates the stack, top = 0 indicates empty stack; ans[] stores answers, default 0 if not found
int top = 0;
for (int i = 1; i <= n; ++i) {
    // When the stack is not empty and the current element is greater than the element corresponding to the stack top, trigger popping
    while (top > 0 && a[i] > a[st[top]]) {
        ans[st[top]] = i; // Settlement: the first greater element on the right for the stack top element is the current position i
        top--;            // Pop
    }
    st[++top] = i;        // Push the current position, waiting for its future fulfiller
}

Proof of Stack State Invariants

Assume that at any stage of the algorithm, the indices of elements in the stack from bottom to top are $p_1, p_2, \dots, p_k$. We prove through mathematical induction that this structure maintains the following two state invariants at all times:

• Invariant 1 (Strictly Increasing Indices): $p_1 < p_2 < \dots < p_k$
• Invariant 2 (Numerically Non-increasing Values): $A[p_1] \ge A[p_2] \ge \dots \ge A[p_k]$

1. Initial State: The stack is empty before scanning, and the invariants trivially hold. When the first element $p_1$ is pushed, the stack contains only one item, and both invariants still hold.
2. Inductive Step (State Transition): Assume the current stack state satisfies the two invariants above. Now a new element $i$ (with $i > p_k$) arrives:
   • Case A: If $A[i] \le A[p_k]$, according to the code logic, the while loop is not triggered, and $i$ is directly pushed to the top. In the new state, the index dimension has $p_k < i$, and the value dimension has $A[p_k] \ge A[i]$. Both invariants are perfectly maintained.
   • Case B: If $A[i] > A[p_k]$, the while loop begins popping. Each popped element $p_{\text{top}}$ logically declares: "$A[i]$ is the first greater element on the right encountered by $A[p_{\text{top}}]$", and records the answer. When the while loop terminates, either the stack is empty (reverting to initial state) or the new stack top satisfies $A[p_{\text{new\_top}}] \ge A[i]$. Then push $i$; both invariants, after dynamic adjustment, are perfectly restored.

NOIP Practical Pitfall Guide

Boundary Control for Array-Simulated Stacks

When using int st[MAXN], top = 0;, ensure that top > 0 before accessing st[top]. In the while loop, top > 0 must be placed on the far left of &&. If the order is incorrectly written due to short-circuit logic (e.g., while(a[i] > a[st[top]] && top > 0)), when the stack is empty, it will first access a[st[0]] or even a[st[-1]], causing Runtime Error (RE).

Symbol Trap Between Strict and Non-Strict Extremes

Establish > or >= strictly according to the problem statement:

• Strictly greater: The pop-triggering condition is a[i] > a[st[top]].
• Non-strictly greater (greater or equal): The triggering condition is a[i] >= a[st[top]]. If the wrong symbol is used in variants requiring strict monotonicity (such as the maximum rectangle in a histogram), it will cause overcounting or undercounting of boundary handling for elements with equal heights, directly leading to WA.

Memory and Constant Optimization

The std::stack underlying implementation uses deque by default, which involves dynamic memory allocation and incurs significant overhead for large datasets. Implementing st[++top] = i and top-- manually incurs no additional overhead and runs more than 3 times faster than STL.

Classic Problem Explanations

Luogu P5788 [Template] Monotonic Stack

• Problem Brief: Given a sequence of positive integers of length $N$, output the index of the first element greater than each element to its right. $N \le 3 \times 10^6$.
• Problem Essence: Standard monotonic stack application. Scan from left to right, exchanging space for time, and amortize the process of finding the next greater element across each push and pop operation.

Core Algorithm Implementation

// Core logic: Linear scan for right-side NGE
for (int i = 1; i <= n; ++i) {
    while (top > 0 && a[i] > a[st[top]]) {
        ans[st[top]] = i; // Settle the answer for the popped element
        top--;
    }
    st[++top] = i; // Push current index
}

Luogu P1191 Rectangles

• Problem Brief: Given an $N \times N$ binary matrix of $0$ and $1$, count the number of sub-rectangles consisting entirely of $1$s. $N \le 400$.

• Problem Essence: A classic counting model combining 2D monotonic stack with dynamic programming.

• Core Solution:

  • Dimensionality Reduction via Hanging Lines: Precompute h[j] representing the number of consecutive 1s upward in column $j$ at the current row (treating each row as the base of a histogram, with h as the current histogram height). If g[i][j] == 0, then h[j] = 0.

  • DP Breakthrough (No Overlap or Omission): Let dp[j] denote the number of all-1 sub-rectangles with the bottom-right corner at column $j$ in the current row. Since every sub-rectangle has one and only one determined bottom-right corner, partitioning the solution set by the bottom-right corner naturally possesses the property of no overlap or omission.

  • Monotonic Stack Accelerates State Transition: Use a monotonic stack to find the first position $k$ to the left that is strictly smaller than $h[j]$ (maintaining a strictly increasing stack).

    • Columns in the interval $[k+1, j]$: their heights are all constrained by the current shortest hanging line $h[j]$, contributing $h[j] \times (j - k)$ new rectangles.
    • Position $k$ and columns to its left: their extensibility has already been limited by the shorter $h[k]$, perfectly inheriting the previous valid state dp[k].

  • State Transition Equation: $$dp[j] = dp[k] + h[j] \times (j - k)$$

Core Algorithm Implementation

// Core logic: Update histogram heights row by row, use monotonic stack to maintain local minima and perform DP transitions
long long total_ans = 0; // Counting problems must use long long

for (int i = 1; i <= n; ++i) {
    int top = 0;
    st[0] = 0; // Key trick: introduce position 0 as a virtual left boundary sentinel, h[0] = 0

    for (int j = 1; j <= n; ++j) {
        // 1. Dynamically update the histogram height for each column in the current row
        h[j] = (g[i][j] == 1) ? h[j] + 1 : 0;

        // 2. Maintain strictly increasing stack, pop when height >= current
        while (top > 0 && h[st[top]] >= h[j]) {
            top--;
        }

        // 3. Now st[top] is the first position k to the left strictly shorter than the current height
        int k = st[top];

        // 4. State transition and accumulate answer
        dp[j] = dp[k] + (long long)h[j] * (j - k);
        total_ans += dp[j];

        st[++top] = j; // Push current column index
    }
}