Monotonic Stack: Efficient Algorithm for Finding Next Greater Element

Core Logic and Mathematical Principles

Monotonic Stack is a linear data structure that achieves $O(N)$ scanning by trading space for time through maintaining the monotonicity of its internal elements. Its core logic lies in promptly eliminating redundant decisions that cannot be the answer, thus optimizing the originally $O(N^2)$ double loop to an amortized $O(1)$.

Taking the problem of finding the "Next Greater Element (NGE)" as an example, let's define the length of the sequence $A$ as $N$. For any position $i$, we need to find the smallest $j$ such that $j > i$ and $A[j] > A[i]$. During the linear scan, if there exists $x < y$ such that $A[x] \\le A[y]$, then for any element to the left of $x$, $A[x]$ can never be its "next greater element", because $A[y]$ is closer and larger. At this point, $A[x]$ becomes a redundant decision and should be popped immediately.

Mathematical induction proof: The Monotonic Stack maintains the indices of elements that have not yet found their answers. Let the indices of elements in the stack from bottom to top be $p_1, p_2, \\dots, p_k$. It must hold that:

$$ p_1 < p_2 < \dots < p_k $$

$$ A[p_1] \ge A[p_2] \ge \dots \ge A[p_k] $$

When a new element $A[i]$ is pushed onto the stack, if $A[i] > A[p_k]$, then the successor maximum of $p_k$ is $i$. Pop $p_k$ and continue comparing with $p_{k-1}$ until the stack is empty or the monotonicity is satisfied, then push $i$ onto the stack. Each element is pushed onto and popped from the stack at most once, resulting in a total time complexity strictly of $O(N)$.

State Design and Algorithm Derivation

In practical implementations, the stack typically stores element indices rather than element values. This is because the index can both index the value via $A[idx]$ and directly calculate the interval length (such as when solving for the maximum rectangle area).

Algorithm flow derivation (taking the first greater element on the right as an example):

Initialize an empty stack st and design an answer array ans initialized to -1.
Traverse the sequence $A$ from left to right, with the current position as $i$.
Loop condition: If the stack is not empty and $A[i] > A[\text{st.top()}]$, it indicates that the current element is the "next greater element" of the stack's top element.
- Record the answer: $\text{ans}[\text{st.top()}] = A[i]$ (or store index $i$).
- Pop the stack top: $\text{st.pop()}$.
- Repeat this step until the stack is empty or $A[i] \\le A[\text{st.top()}]$.
Push the current index $i$ onto the stack: $\text{st.push}(i)$.
At the end of the traversal, the remaining elements in the stack will have ans still as -1, indicating there are no greater elements on the right.

If the requirement is for the "first smaller element on the left", simply change the traversal direction to left-to-right and modify the popping condition to $A[i] \\le A[\text{st.top()}]$ to maintain a monotonic increasing stack. Essentially, this utilizes the duality of symbols.

C++ Standard Source Code (NOIP Style)

#include <iostream>
#include <vector>
#include <stack>

using namespace std;

// Solve for the index of the first strictly greater element on the right of each element, -1 if it doesn't exist
vector<int> getNextGreaterElement(const vector<int>& A) {
    int n = A.size();
    vector<int> ans(n, -1);
    stack<int> st; // The stack stores indices, strictly decreasing values from bottom to top

    for (int i = 0; i < n; ++i) {
        // Must use while loop to continuously eliminate all stack tops that are less than the current element
        while (!st.empty() && A[i] > A[st.top()]) {
            ans[st.top()] = i; // Record the current index that triggers the pop as the answer
            st.pop();
        }
        st.push(i); // The current index must be pushed onto the stack as a potential comparison target for subsequent elements
    }
    return ans;
}

int main() {
    // Improve IO performance to prevent TLE due to std::endl or cin under large data in NOIP
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    if (!(cin >> n)) return 0;

    vector<int> A(n);
    for (int i = 0; i < n; ++i) {
        cin >> A[i];
    }

    vector<int> ans = getNextGreaterElement(A);

    for (int i = 0; i < n; ++i) {
        // Output the corresponding element value, -1 if it doesn't exist
        if (ans[i] != -1) {
            cout << A[ans[i]] << (i == n - 1 ? "" : " ");
        } else {
            cout << -1 << (i == n - 1 ? "" : " ");
        }
    }
    cout << "\n";

    return 0;
}

NOIP Practical Pitfall Guide

Out-of-bounds check in empty stack state (Segment Fault) When determining the popping condition in the while loop, !st.empty() must be placed on the left side of the logical AND &&. If you first access A[st.top()] and then check if the stack is empty, it will lead to illegal memory access when the stack is empty, directly causing the judge to return RE (runtime error).
Infinite loop and logical errors due to consecutive equal symbols Pay attention to the boundary choice between "greater than" $A[i] > A[\text{st.top()}]$ and "greater than or equal to" $A[i] \\ge A[\text{st.top()}]$. If the problem requires strict greater than, but you mistakenly write $\ge$, it will lead to elements being incorrectly popped. In some variant problems (such as calculating rectangle areas), if the logic for popping is not correctly designed when handling elements of the same height, it may result in an inability to exit the while loop, causing TLE or even infinite loops.
Space overhead optimization (array simulating stack) The default underlying structure of STL's std::stack is std::deque, and frequent memory allocations have constant overhead. Under the extreme time limits of NOIP, it is recommended to use a native array to simulate the stack: int st[MAXN], top = 0;. Replace push with st[++top] = i and pop with top--. This can bring nearly 3 times constant-level acceleration.

Classic NOIP/Luogu Problems

1. Luogu P5788 [Template] Monotonic Stack

Problem Description: Given a positive integer sequence of length $N$, output the index of the first element greater than each element after it. $N \le 3 \times 10^6$.
Core Idea: Standard monotonic stack template problem. Due to the data size reaching $3 \times 10^6$, it is necessary to use native arrays to simulate the stack and use scanf or fast input (Fast IO). Maintain a monotonically decreasing stack (storing indices), when the new element is greater than the top element of the stack, the index of this new element is the answer for the top element.

2. Luogu P1191 Rectangle

Problem Description: Given an $N \times N$ binary matrix of $01$, find the number of submatrices that are entirely composed of $1$s. $N \le 400$.
Core Idea: Two-dimensional monotonic stack problem. By using the hanging line method, preprocess the number of consecutive $1$s above each point to serve as the "height" of that position in the current row. For each row, the problem transforms into finding the number of submatrices in a histogram. By using the monotonic stack to find the first position on both sides that is lower than each position in $O(N)$ time, we can quickly solve it using mathematical combination formulas within a total time complexity of $O(N^2)$, avoiding the $O(N^4)$ brute force enumeration.